Number Spiral

CSES - Number Spiral

Time limit: 1.00 s
Memory limit: 512 MB

A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:

Your task is to find out the number in row

y

$y$ and column

x

$x$ .

Input

The first input line contains an integer

t

$t$ : the number of tests.

After this, there are

t

$t$ lines, each containing integers

y

$y$ and

x

$x$ .

Output

For each test, print the number in row

y

$y$ and column

x

$x$ .

Constraints

$1 \le t \le 10^5$
$1 \le y,x \le 10^9$

Example

Input:

Output:

CSES - Two Knights

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count for

k = 1, 2, \dots, n

$k=1,2,\ldots,n$ the number of ways two knights can be placed on a

k \times k

$k \times k$ chessboard so that they do not attack each other.

Input

The only input line contains an integer

n

$n$ .

Output

Print

n

$n$ integers: the results.

Constraints

$1 \le n \le 10000$

Example

Input:
8

Output:

CSES - Two Sets

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to divide the numbers

1, 2, \dots, n

$1,2,\ldots,n$ into two sets of equal sum.

Input

The only input line contains an integer

n

$n$ .

Output

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints

$1 \le n \le 10^6$

Example 1

Input:
7

Output:

Example 2

Input:
6

Output:
NO

Bit Strings

CSES - Bit Strings

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the number of bit strings of length

n

$n$ .

For example, if

n = 3

$n=3$ , the correct answer is

8

$8$ , because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Input

The only input line has an integer

n

$n$ .

Output

Print the result modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^6$

Example

Input:
3

Output:
8

Trailing Zeroes

CSES - Trailing Zeros

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the number of trailing zeros in the factorial

n!

$n!$ .

For example,

20! = 2432902008176640000

$20!=2432902008176640000$ and it has

4

$4$ trailing zeros.

Input

The only input line has an integer

n

$n$ .

Output

Print the number of trailing zeros in

n!

$n!$ .

Constraints

$1 \le n \le 10^9$

Example

Input:
20

Output:
4

Coin Piles

CSES - Coin Piles

Time limit: 1.00 s
Memory limit: 512 MB

You have two coin piles containing

a

$a$ and

b

$b$ coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.

Your task is to efficiently find out if you can empty both the piles.

Input

The first input line has an integer

t

$t$ : the number of tests.

After this, there are

t

$t$ lines, each of which has two integers

a

$a$ and

b

$b$ : the numbers of coins in the piles.

Output

For each test, print "YES" if you can empty the piles and "NO" otherwise.

Constraints

$1 \le t \le 10^5$
$0 \le a, b \le 10^9$

Example

Input:

Output:

YES

NO

YES

Palinderome Reorder

CSES - Palindrome Reorder

Time limit: 1.00 s
Memory limit: 512 MB

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backwards).

Input

The only input line has a string of length

n

$n$ consisting of characters A–Z.

Output

Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTION".

Constraints

$1 \le n \le 10^6$

Example

Input:
AAAACACBA

Output:
AACABACAA

Gray Code

CSES - Gray Code

Time limit: 1.00 s
Memory limit: 512 MB

A Gray code is a list of all

2^{n}

$2^n$ bit strings of length

n

$n$ , where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length

n

$n$ .

Input

The only input line has an integer

n

$n$ .

Output

Print

2^{n}

$2^n$ lines that describe the Gray code. You can print any valid solution.

Constraints

$1 \le n \le 16$

Example

Input:
2

Output:

Tower of Hanoi

CSES - Gray Code

Time limit: 1.00 s
Memory limit: 512 MB

A Gray code is a list of all

2^{n}

$2^n$ bit strings of length

n

$n$ , where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one).

Your task is to create a Gray code for a given length

n

$n$ .

Input

The only input line has an integer

n

$n$ .

Output

Print

2^{n}

$2^n$ lines that describe the Gray code. You can print any valid solution.

Constraints

$1 \le n \le 16$

Example

Input:
2

Output:

Tower of Hanoi

CSES - Tower of Hanoi

Time limit: 1.00 s
Memory limit: 512 MB

The Tower of Hanoi game consists of three stacks (left, middle and right) and

n

$n$ round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom.

The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.

Your task is to find a solution that minimizes the number of moves.

Input

The only input line has an integer

n

$n$ : the number of disks.

Output

First print an integer

k

$k$ : the minimum number of moves.

After this, print

k

$k$ lines that describe the moves. Each line has two integers

a

$a$ and

b

$b$ : you move a disk from stack

a

$a$ to stack

b

$b$ .

Constraints

$1 \le n \le 16$

Example

Input:
2

Output:

Creating Strings

CSES - Creating Strings

Time limit: 1.00 s
Memory limit: 512 MB

Given a string, your task is to generate all different strings that can be created using its characters.

Input

The only input line has a string of length

n

$n$ . Each character is between a–z.

Output

First print an integer

k

$k$ : the number of strings. Then print

k

$k$ lines: the strings in alphabetical order.

Constraints

$1 \le n \le 8$

Example

Input:
aabac

Output:

20

aaabc

aaacb

aabac

aabca

aacab

aacba

abaac

abaca

abcaa

acaab

acaba

acbaa

baaac

baaca

bacaa

bcaaa

caaab

caaba

cabaa

cbaaa

Apple Division

CSES - Apple Division

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer

n

$n$ : the number of apples.

The next line has

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\dots,p_n$ : the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints

$1 \le n \le 20$
$1 \le p_i \le 10^9$

Example

Input:

5

3 2 7 4 1

Output:
1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

Chessboard and Queens

CSES - Chessboard and Queens

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

Input

The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).

Output

Print one integer: the number of ways you can place the queens.

Example

Input:

........

........

..*.....

........

........

.....**.

...*....

........

Output:
65

Digit Queries

CSES - Digit Queries

Time limit: 1.00 s
Memory limit: 512 MB

Consider an infinite string that consists of all positive integers in increasing order:

12345678910111213141516171819202122232425...

Your task is to process

q

$q$ queries of the form: what is the digit at position

k

$k$ in the string?

Input

The first input line has an integer

q

$q$ : the number of queries.

After this, there are

q

$q$ lines that describe the queries. Each line has an integer

k

$k$ : a

1

$1$ -indexed position in the string.

Output

For each query, print the corresponding digit.

Constraints

$1 \le q \le 1000$
$1 \le k \le 10^{18}$

Example

Input:

Output:

Grid Paths

CSES - Grid Paths

Time limit: 1.00 s
Memory limit: 512 MB

There are

88418

$88418$ paths in a

7 \times 7

$7 \times 7$ grid from the upper-left square to the lower-left square. Each path corresponds to a

48

$48$ -character description consisting of characters D (down), U (up), L (left) and R (right).

For example, the path

corresponds to the description DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

You are given a description of a path which may also contain characters ? (any direction). Your task is to calculate the number of paths that match the description.

Input

The only input line has a

48

$48$ -character string of characters ?, D, U, L and R.

Output

Print one integer: the total number of paths.

Example

Input:
??????R??????U??????????????????????????LD????D?

Output:
201

Sorting and Searching

Distinct Numbers

CSES - Distinct Numbers

Time limit: 1.00 s
Memory limit: 512 MB

You are given a list of

n

$n$ integers, and your task is to calculate the number of distinct values in the list.

Input

The first input line has an integer

n

$n$ : the number of values.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ .

Output

Print one integers: the number of distinct values.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

5

2 3 2 2 3

Output:
2

Apartments

CSES - Apartments

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ applicants and

m

$m$ free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

The first input line has three integers

n

$n$ ,

m

$m$ , and

k

$k$ : the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \ldots, a_n$ : the desired apartment size of each applicant. If the desired size of an applicant is

x

$x$ , he or she will accept any apartment whose size is between

x - k

$x-k$ and

x + k

$x+k$ .

The last line contains

m

$m$ integers

b_{1}, b_{2}, \dots, b_{m}

$b_1, b_2, \ldots, b_m$ : the size of each apartment.

Output

Print one integer: the number of applicants who will get an apartment.

Constraints

$1 \le n, m \le 2 \cdot 10^5$
$0 \le k \le 10^9$
$1 \le a_i, b_i \le 10^9$

Example

Input:

4 3 5

60 45 80 60

30 60 75

Output:
2

Ferris Wheel

CSES - Ferris Wheel

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ children who want to go to a Ferris wheel, and your task is to find a gondola for each child.

Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed

x

$x$ . You know the weight of every child.

What is the minimum number of gondolas needed for the children?

Input

The first input line contains two integers

n

$n$ and

x

$x$ : the number of children and the maximum allowed weight.

The next line contains

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\ldots,p_n$ : the weight of each child.

Output

Print one integer: the minimum number of gondolas.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x \le 10^9$
$1 \le p_i \le x$

Example

Input:

4 10

7 2 3 9

Output:
3

Concert Tickets

CSES - Concert Tickets

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ concert tickets available, each with a certain price. Then,

m

$m$ customers arrive, one after another.

Each customer announces the maximum price they are willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

Input

The first input line contains integers

n

$n$ and

m

$m$ : the number of tickets and the number of customers.

The next line contains

n

$n$ integers

h_{1}, h_{2}, \dots, h_{n}

$h_1,h_2,\ldots,h_n$ : the price of each ticket.

The last line contains

m

$m$ integers

t_{1}, t_{2}, \dots, t_{m}

$t_1,t_2,\ldots,t_m$ : the maximum price for each customer in the order they arrive.

Output

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

If a customer cannot get any ticket, print

- 1

$-1$ .

Constraints

$1 \le n, m \le 2 \cdot 10^5$
$1 \le h_i, t_i \le 10^9$

Example

Input:

Output:

Restaurant Customers

CSES - Restaurant Customers

Time limit: 1.00 s
Memory limit: 512 MB

You are given the arrival and leaving times of

n

$n$ customers in a restaurant.

What was the maximum number of customers in the restaurant at any time?

Input

The first input line has an integer

n

$n$ : the number of customers.

After this, there are

n

$n$ lines that describe the customers. Each line has two integers

a

$a$ and

b

$b$ : the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

Output

Print one integer: the maximum number of customers.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a < b \le 10^9$

Example

Input:

Output:
2

Movie Festival

CSES - Movie Festival

Time limit: 1.00 s
Memory limit: 512 MB

In a movie festival

n

$n$ movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?

Input

The first input line has an integer

n

$n$ : the number of movies.

After this, there are

n

$n$ lines that describe the movies. Each line has two integers

a

$a$ and

b

$b$ : the starting and ending times of a movie.

Output

Print one integer: the maximum number of movies.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a < b \le 10^9$

Example

Input:

Output:
2

Sum of Two Values

CSES - Sum of Two Values

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ integers, and your task is to find two values (at distinct positions) whose sum is

x

$x$ .

Input

The first input line has two integers

n

$n$ and

x

$x$ : the array size and the target sum.

The second line has

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1,a_2,\dots,a_n$ : the array values.

Output

Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x,a_i \le 10^9$

Example

Input:

4 8

2 7 5 1

Output:
2 4

Maximum Subarray Sum

CSES - Maximum Subarray Sum

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

Input

The first input line has an integer

n

$n$ : the size of the array.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Output

Print one integer: the maximum subarray sum.

Constraints

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le x_i \le 10^9$

Example

Input:

8

-1 3 -2 5 3 -5 2 2

Output:
9

Stick Lengths

CSES - Stick Lengths

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.

You can either lengthen and shorten each stick. Both operations cost

x

$x$ where

x

$x$ is the difference between the new and original length.

What is the minimum total cost?

Input

The first input line contains an integer

n

$n$ : the number of sticks.

Then there are

n

$n$ integers:

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\ldots,p_n$ : the lengths of the sticks.

Output

Print one integer: the minimum total cost.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le p_i \le 10^9$

Example

Input:

5

2 3 1 5 2

Output:
5

Missing Coin Sum

CSES - Missing Coin Sum

Time limit: 1.00 s
Memory limit: 512 MB

You have

n

$n$ coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?

Input

The first input line has an integer

n

$n$ : the number of coins.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the value of each coin.

Output

Print one integer: the smallest coin sum.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

5

2 9 1 2 7

Output:
6

Collecting NUmbers

CSES - Collecting Numbers

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array that contains each number between

1 \dots n

$1 \dots n$ exactly once. Your task is to collect the numbers from

1

$1$ to

n

$n$ in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible. What will be the total number of rounds?

Input

The first line has an integer

n

$n$ : the array size.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the numbers in the array.

Output

Print one integer: the number of rounds.

Constraints

$1 \le n \le 2 \cdot 10^5$

Example

Input:

5

4 2 1 5 3

Output:
3

Collecting Numbers II

CSES - Collecting Numbers II

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array that contains each number between

1 \dots n

$1 \dots n$ exactly once. Your task is to collect the numbers from

1

$1$ to

n

$n$ in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible.

Given

m

$m$ operations that swap two numbers in the array, your task is to report the number of rounds after each operation.

Input

The first line has two integers

n

$n$ and

m

$m$ : the array size and the number of operations.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the numbers in the array.

Finally, there are

m

$m$ lines that describe the operations. Each line has two integers

a

$a$ and

b

$b$ : the numbers at positions

a

$a$ and

b

$b$ are swapped.

Output

Print

m

$m$ integers: the number of rounds after each swap.

Constraints

$1 \le n, m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

PLaylist

CSES - Playlist

Time limit: 1.00 s
Memory limit: 512 MB

You are given a playlist of a radio station since its establishment. The playlist has a total of

n

$n$ songs.

What is the longest sequence of successive songs where each song is unique?

Input

The first input line contains an integer

n

$n$ : the number of songs.

The next line has

n

$n$ integers

k_{1}, k_{2}, \dots, k_{n}

$k_1,k_2,\ldots,k_n$ : the id number of each song.

Output

Print the length of the longest sequence of unique songs.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le k_i \le 10^9$

Example

Input:

8

1 2 1 3 2 7 4 2

Output:
5

Towers

CSES - Towers

Time limit: 1.00 s
Memory limit: 512 MB

You are given

n

$n$ cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

Input

The first input line contains an integer

n

$n$ : the number of cubes.

The next line contains

n

$n$ integers

k_{1}, k_{2}, \dots, k_{n}

$k_1,k_2,\ldots,k_n$ : the sizes of the cubes.

Output

Print one integer: the minimum number of towers.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le k_i \le 10^9$

Example

Input:

5

3 8 2 1 5

Output:
2

Traffic Lights

CSES - Traffic Lights

Time limit: 1.00 s
Memory limit: 512 MB

There is a street of length

x

$x$ whose positions are numbered

0, 1, \dots, x

$0,1,\ldots,x$ . Initially there are no traffic lights, but

n

$n$ sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Input

The first input line contains two integers

x

$x$ and

n

$n$ : the length of the street and the number of sets of traffic lights.

Then, the next line contains

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\ldots,p_n$ : the position of each set of traffic lights. Each position is distinct.

Output

Print the length of the longest passage without traffic lights after each addition.

Constraints

$1 \le x \le 10^9$
$1 \le n \le 2 \cdot 10^5$
$0 < p_i < x$

Example

Input:

8 3

3 6 2

Output:
5 3 3

Joshephus Problem I

CSES - Josephus Problem I

Time limit: 1.00 s
Memory limit: 512 MB

Consider a game where there are

n

$n$ children (numbered

1, 2, \dots, n

$1,2,\dots,n$ ) in a circle. During the game, every second child is removed from the circle, until there are no children left. In which order will the children be removed?

Input

The only input line has an integer

n

$n$ .

Output

Print

n

$n$ integers: the removal order.

Constraints

$1 \le n \le 2 \cdot 10^5$

Example

Input:
7

Output:
2 4 6 1 5 3 7

Joshephus Problem II

CSES - Josephus Problem II

Time limit: 1.00 s
Memory limit: 512 MB

Consider a game where there are

n

$n$ children (numbered

1, 2, \dots, n

$1,2,\dots,n$ ) in a circle. During the game, repeatedly

k

$k$ children are skipped and one child is removed from the circle. In which order will the children be removed?

Input

The only input line has two integers

n

$n$ and

k

$k$ .

Output

Print

n

$n$ integers: the removal order.

Constraints

$1 \le n \le 2 \cdot 10^5$
$0 \le k \le 10^9$

Example

Input:
7 2

Output:
3 6 2 7 5 1 4

Nested Ranges Check

CSES - Nested Ranges Check

Time limit: 1.00 s
Memory limit: 512 MB

Given

n

$n$ ranges, your task is to determine for each range if it contains some other range and if some other range contains it.

Range

[a, b]

$[a,b]$ contains range

[c, d]

$[c,d]$ if

a \leq c

$a \le c$ and

d \leq b

$d \le b$ .

Input

The first input line has an integer

n

$n$ : the number of ranges.

After this, there are

n

$n$ lines that describe the ranges. Each line has two integers

x

$x$ and

y

$y$ : the range is

[x, y]

$[x,y]$ .

You may assume that no range appears more than once in the input.

Output

First print a line that describes for each range (in the input order) if it contains some other range (1) or not (0).

Then print a line that describes for each range (in the input order) if some other range contains it (1) or not (0).

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x < y \le 10^9$

Example

Input:

Output:

1 0 0 0

0 1 0 1

Nested Ranges Count

CSES - Nested Ranges Count

Time limit: 1.00 s
Memory limit: 512 MB

Given

n

$n$ ranges, your task is to count for each range how many other ranges it contains and how many other ranges contain it.

Range

[a, b]

$[a,b]$ contains range

[c, d]

$[c,d]$ if

a \leq c

$a \le c$ and

d \leq b

$d \le b$ .

Input

The first input line has an integer

n

$n$ : the number of ranges.

After this, there are

n

$n$ lines that describe the ranges. Each line has two integers

x

$x$ and

y

$y$ : the range is

[x, y]

$[x,y]$ .

You may assume that no range appears more than once in the input.

Output

First print a line that describes for each range (in the input order) how many other ranges it contains.

Then print a line that describes for each range (in the input order) how many other ranges contain it.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x < y \le 10^9$

Example

Input:

Output:

2 0 0 0

0 1 0 1

Room Allocation

CSES - Room Allocation

Time limit: 1.00 s
Memory limit: 512 MB

There is a large hotel, and

n

$n$ customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

Input

The first input line contains an integer

n

$n$ : the number of customers.

Then there are

n

$n$ lines, each of which describes one customer. Each line has two integers

a

$a$ and

b

$b$ : the arrival and departure day.

Output

Print first an integer

k

$k$ : the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered

1, 2, \dots, k

$1,2,\ldots,k$ . You can print any valid solution.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a \le b \le 10^9$

Example

Input:

Output:

2

1 2 1

Factory Machines

CSES - Factory Machines

Time limit: 1.00 s
Memory limit: 512 MB

A factory has

n

$n$ machines which can be used to make products. Your goal is to make a total of

t

$t$ products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make

t

$t$ products?

Input

The first input line has two integers

n

$n$ and

t

$t$ : the number of machines and products.

The next line has

n

$n$ integers

k_{1}, k_{2}, \dots, k_{n}

$k_1,k_2,\dots,k_n$ : the time needed to make a product using each machine.

Output

Print one integer: the minimum time needed to make

t

$t$ products.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le t \le 10^9$
$1 \le k_i \le 10^9$

Example

Input:

3 7

3 2 5

Output:
8

Explanation: Machine 1 makes two products, machine 2 makes four products and machine 3 makes one product.

Task and Deadlines

CSES - Tasks and Deadlines

Time limit: 1.00 s
Memory limit: 512 MB

You have to process

n

$n$ tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is

d - f

$d-f$ where

d

$d$ is its deadline and

f

$f$ is your finishing time. (The starting time is

0

$0$ , and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

Input

The first input line has an integer

n

$n$ : the number of tasks.

After this, there are

n

$n$ lines that describe the tasks. Each line has two integers

a

$a$ and

d

$d$ : the duration and deadline of the task.

Output

Print one integer: the maximum reward.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,d \le 10^6$

Example

Input:

Output:
2

Reading Books

CSES - Reading Books

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ books, and Kotivalo and Justiina are going to read them all. For each book, you know the time it takes to read it.

They both read each book from beginning to end, and they cannot read a book at the same time. What is the minimum total time required?

Input

The first input line has an integer

n

$n$ : the number of books.

The second line has

n

$n$ integers

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\dots,t_n$ : the time required to read each book.

Output

Print one integer: the minimum total time.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le t_i \le 10^9$

Example

Input:

3

2 8 3

Output:
16

Sum Of Three Values

CSES - Sum of Three Values

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ integers, and your task is to find three values (at distinct positions) whose sum is

x

$x$ .

Input

The first input line has two integers

n

$n$ and

x

$x$ : the array size and the target sum.

The second line has

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1,a_2,\dots,a_n$ : the array values.

Output

Print three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints

$1 \le n \le 5000$
$1 \le x,a_i \le 10^9$

Example

Input:

4 8

2 7 5 1

Output:
1 3 4

Sum of Four Values

CSES - Sum of Four Values

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ integers, and your task is to find four values (at distinct positions) whose sum is

x

$x$ .

Input

The first input line has two integers

n

$n$ and

x

$x$ : the array size and the target sum.

The second line has

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1,a_2,\dots,a_n$ : the array values.

Output

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

Constraints

$1 \le n \le 1000$
$1 \le x,a_i \le 10^9$

Example

Input:

8 15

3 2 5 8 1 3 2 3

Output:
2 4 6 7

Nearest Smaller Values

CSES - Nearest Smaller Values

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to find for each array position the nearest position to its left having a smaller value.

Input

The first input line has an integer

n

$n$ : the size of the array.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Output

Print

n

$n$ integers: for each array position the nearest position with a smaller value. If there is no such position, print

0

$0$ .

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

8

2 5 1 4 8 3 2 5

Output:
0 1 0 3 4 3 3 7

Subarray Sums I

CSES - Subarray Sums I

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ positive integers, your task is to count the number of subarrays having sum

x

$x$ .

Input

The first input line has two integers

n

$n$ and

x

$x$ : the size of the array and the target sum

x

$x$ .

The next line has

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1,a_2,\dots,a_n$ : the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x,a_i \le 10^9$

Example

Input:

5 7

2 4 1 2 7

Output:
3

Subarray Sums II

CSES - Subarray Sums II

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to count the number of subarrays having sum

x

$x$ .

Input

The first input line has two integers

n

$n$ and

x

$x$ : the size of the array and the target sum

x

$x$ .

The next line has

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1,a_2,\dots,a_n$ : the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le x,a_i \le 10^9$

Example

Input:

5 7

2 -1 3 5 -2

Output:
2

Subarray Divisibility

CSES - Subarray Divisibility

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to count the number of subarrays where the sum of values is divisible by

n

$n$ .

Input

The first input line has an integer

n

$n$ : the size of the array.

The next line has

n

$n$ integers

a_{1}, a_{2}, \dots, a_{n}

$a_1,a_2,\dots,a_n$ : the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le a_i \le 10^9$

Example

Input:

5

3 1 2 7 4

Output:
1

Subarray Distinct Values

CSES - Subarray Distinct Values

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to calculate the number of subarrays that have at most

k

$k$ distinct values.

Input

The first input line has two integers

n

$n$ and

k

$k$ .

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the contents of the array.

Output

Print one integer: the number of subarrays.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

5 2

1 2 3 1 1

Output:
10

Array Division

CSES - Array Division

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array containing

n

$n$ positive integers.

Your task is to divide the array into

k

$k$ subarrays so that the maximum sum in a subarray is as small as possible.

Input

The first input line contains two integers

n

$n$ and

k

$k$ : the size of the array and the number of subarrays in the division.

The next line contains

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Print one integer: the maximum sum in a subarray in the optimal division.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le k \le n$
$1 \le x_i \le 10^9$

Example

Input:

5 3

2 4 7 3 5

Output:
8

Explanation: An optimal division is

[2, 4], [7], [3, 5]

$[2,4],[7],[3,5]$ where the sums of the subarrays are

6, 7, 8

$6,7,8$ . The largest sum is the last sum

8

$8$ .

Sliding Median

CSES - Sliding Median

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ integers. Your task is to calculate the median of each window of

k

$k$ elements, from left to right.

The median is the middle element when the elements are sorted. If the number of elements is even, there are two possible medians and we assume that the median is the smaller of them.

Input

The first input line contains two integers

n

$n$ and

k

$k$ : the number of elements and the size of the window.

Then there are

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Print

n - k + 1

$n-k+1$ values: the medians.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

8 3

2 4 3 5 8 1 2 1

Output:
3 4 5 5 2 1

Sliding Cost

CSES - Sliding Cost

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ integers. Your task is to calculate for each window of

k

$k$ elements, from left to right, the minimum total cost of making all elements equal.

You can increase or decrease each element with cost

x

$x$ where

x

$x$ is the difference between the new and the original value. The total cost is the sum of such costs.

Input

The first input line contains two integers

n

$n$ and

k

$k$ : the number of elements and the size of the window.

Then there are

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Output

n - k + 1

$n-k+1$ values: the costs.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

8 3

2 4 3 5 8 1 2 1

Output:
2 2 5 7 7 1

Movie Festival II

CSES - Movie Festival II

Time limit: 1.00 s
Memory limit: 512 MB

In a movie festival,

n

$n$ movies will be shown. Syrjälä's movie club consists of

k

$k$ members, who will be all attending the festival.

You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?

Input

The first input line has two integers

n

$n$ and

k

$k$ : the number of movies and club members.

After this, there are

n

$n$ lines that describe the movies. Each line has two integers

a

$a$ and

b

$b$ : the starting and ending time of a movie.

Output

Print one integer: the maximum total number of movies.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le a < b \le 10^9$

Example

Input:

Output:
4

Maximum Subarraysum II

CSES - Maximum Subarray Sum II

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to find the maximum sum of values in a contiguous subarray with length between

a

$a$ and

b

$b$ .

Input

The first input line has three integers

n

$n$ ,

a

$a$ and

b

$b$ : the size of the array and the minimum and maximum subarray length.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Output

Print one integer: the maximum subarray sum.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a \le b \le n$
$-10^9 \le x_i \le 10^9$

Example

Input:

8 1 2

-1 3 -2 5 3 -5 2 2

Output:
8

Dynamic Programming

Dice Combinations

CSES - Dice Combinations

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count the number of ways to construct sum

n

$n$ by throwing a dice one or more times. Each throw produces an outcome between

1

$1$ and

6

$6$ .

For example, if

n = 3

$n=3$ , there are

4

$4$ ways:

$1+1+1$
$1+2$
$2+1$
$3$

Input

The only input line has an integer

n

$n$ .

Output

Print the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^6$

Example

Input:
3

Output:
4

Minimizing Coins

CSES - Minimizing Coins

Time limit: 1.00 s
Memory limit: 512 MB

Consider a money system consisting of

n

$n$ coins. Each coin has a positive integer value. Your task is to produce a sum of money

x

$x$ using the available coins in such a way that the number of coins is minimal.

For example, if the coins are

{1, 5, 7}

$\{1,5,7\}$ and the desired sum is

11

$11$ , an optimal solution is

5 + 5 + 1

$5+5+1$ which requires

3

$3$ coins.

Input

The first input line has two integers

n

$n$ and

x

$x$ : the number of coins and the desired sum of money.

The second line has

n

$n$ distinct integers

c_{1}, c_{2}, \dots, c_{n}

$c_1,c_2,\dots,c_n$ : the value of each coin.

Output

Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print

- 1

$-1$ .

Constraints

$1 \le n \le 100$
$1 \le x \le 10^6$
$1 \le c_i \le 10^6$

Example

Input:

3 11

1 5 7

Output:
3

Coin Combinations I

CSES - Coin Combinations I

Time limit: 1.00 s
Memory limit: 512 MB

Consider a money system consisting of

n

$n$ coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum

x

$x$ using the available coins.

For example, if the coins are

{2, 3, 5}

$\{2,3,5\}$ and the desired sum is

9

$9$ , there are

8

$8$ ways:

$2+2+5$
$2+5+2$
$5+2+2$
$3+3+3$
$2+2+2+3$
$2+2+3+2$
$2+3+2+2$
$3+2+2+2$

Input

The first input line has two integers

n

$n$ and

x

$x$ : the number of coins and the desired sum of money.

The second line has

n

$n$ distinct integers

c_{1}, c_{2}, \dots, c_{n}

$c_1,c_2,\dots,c_n$ : the value of each coin.

Output

Print one integer: the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 100$
$1 \le x \le 10^6$
$1 \le c_i \le 10^6$

Example

Input:

3 9

2 3 5

Output:
8

Coin COmbinations II

CSES - Coin Combinations II

Time limit: 1.00 s
Memory limit: 512 MB

Consider a money system consisting of

n

$n$ coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum

x

$x$ using the available coins.

For example, if the coins are

{2, 3, 5}

$\{2,3,5\}$ and the desired sum is

9

$9$ , there are

3

$3$ ways:

$2+2+5$
$3+3+3$
$2+2+2+3$

Input

The first input line has two integers

n

$n$ and

x

$x$ : the number of coins and the desired sum of money.

The second line has

n

$n$ distinct integers

c_{1}, c_{2}, \dots, c_{n}

$c_1,c_2,\dots,c_n$ : the value of each coin.

Output

Print one integer: the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 100$
$1 \le x \le 10^6$
$1 \le c_i \le 10^6$

Example

Input:

3 9

2 3 5

Output:
3

Removing Digits

CSES - Removing Digits

Time limit: 1.00 s
Memory limit: 512 MB

You are given an integer

n

$n$ . On each step, you may subtract one of the digits from the number.

How many steps are required to make the number equal to

0

$0$ ?

Input

The only input line has an integer

n

$n$ .

Output

Print one integer: the minimum number of steps.

Constraints

$1 \le n \le 10^6$

Example

Input:
27

Output:
5

Explanation: An optimal solution is

27 \to 20 \to 18 \to 10 \to 9 \to 0

$27 \rightarrow 20 \rightarrow 18 \rightarrow 10 \rightarrow 9 \rightarrow 0$ .

Grid Paths

CSES - Grid Paths

Time limit: 1.00 s
Memory limit: 512 MB

Consider an

n \times n

$n \times n$ grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square. You can only move right or down.

Input

The first input line has an integer

n

$n$ : the size of the grid.

After this, there are

n

$n$ lines that describe the grid. Each line has

n

$n$ characters: . denotes an empty cell, and * denotes a trap.

Output

Print the number of paths modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 1000$

Example

Input:

4

....

.*..

...*

*...

Output:
3

Book Shop

CSES - Book Shop

Time limit: 1.00 s
Memory limit: 512 MB

You are in a book shop which sells

n

$n$ different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most

x

$x$ . What is the maximum number of pages you can buy? You can buy each book at most once.

Input

The first input line contains two integers

n

$n$ and

x

$x$ : the number of books and the maximum total price.

The next line contains

n

$n$ integers

h_{1}, h_{2}, \dots, h_{n}

$h_1,h_2,\ldots,h_n$ : the price of each book.

The last line contains

n

$n$ integers

s_{1}, s_{2}, \dots, s_{n}

$s_1,s_2,\ldots,s_n$ : the number of pages of each book.

Output

Print one integer: the maximum number of pages.

Constraints

$1 \le n \le 1000$
$1 \le x \le 10^5$
$1 \le h_i, s_i \le 1000$

Example

Input:

Output:
13

Explanation: You can buy books 1 and 3. Their price is

4 + 5 = 9

$4+5=9$ and the number of pages is

5 + 8 = 13

$5+8=13$ .

Array Description

CSES - Array Description

Time limit: 1.00 s
Memory limit: 512 MB

You know that an array has

n

$n$ integers between

1

$1$ and

m

$m$ , and the absolute difference between two adjacent values is at most

1

$1$ .

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the array size and the upper bound for each value.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the contents of the array. Value

0

$0$ denotes an unknown value.

Output

Print one integer: the number of arrays modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^5$
$1 \le m \le 100$
$0 \le x_i \le m$

Example

Input:

3 5

2 0 2

Output:
3

Explanation: The arrays

[2, 1, 2]

$[2,1,2]$ ,

[2, 2, 2]

$[2,2,2]$ and

[2, 3, 2]

$[2,3,2]$ match the description.

Counting Towers

CSES - Array Description

Time limit: 1.00 s
Memory limit: 512 MB

You know that an array has

n

$n$ integers between

1

$1$ and

m

$m$ , and the absolute difference between two adjacent values is at most

1

$1$ .

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the array size and the upper bound for each value.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the contents of the array. Value

0

$0$ denotes an unknown value.

Output

Print one integer: the number of arrays modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^5$
$1 \le m \le 100$
$0 \le x_i \le m$

Example

Input:

3 5

2 0 2

Output:
3

Explanation: The arrays

[2, 1, 2]

$[2,1,2]$ ,

[2, 2, 2]

$[2,2,2]$ and

[2, 3, 2]

$[2,3,2]$ match the description.

Edit Distance

CSES - Edit Distance

Time limit: 1.00 s
Memory limit: 512 MB

The edit distance between two strings is the minimum number of operations required to transform one string into the other.

The allowed operations are:

Add one character to the string.
Remove one character from the string.
Replace one character in the string.

For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.

Your task is to calculate the edit distance between two strings.

Input

The first input line has a string that contains

n

$n$ characters between A–Z.

The second input line has a string that contains

m

$m$ characters between A–Z.

Output

Print one integer: the edit distance between the strings.

Constraints

$1 \le n,m \le 5000$

Example

Input:

LOVE

MOVIE

Output:
2

Rectangle Cutting

CSES - Rectangle Cutting

Time limit: 1.00 s
Memory limit: 512 MB

Given an

a \times b

$a \times b$ rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves?

Input

The only input line has two integers

a

$a$ and

b

$b$ .

Output

Print one integer: the minimum number of moves.

Constraints

$1 \le a,b \le 500$

Example

Input:
3 5

Output:
3

Money Sums

CSES - Money Sums

Time limit: 1.00 s
Memory limit: 512 MB

You have

n

$n$ coins with certain values. Your task is to find all money sums you can create using these coins.

Input

The first input line has an integer

n

$n$ : the number of coins.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the values of the coins.

Output

First print an integer

k

$k$ : the number of distinct money sums. After this, print all possible sums in increasing order.

Constraints

$1 \le n \le 100$
$1 \le x_i \le 1000$

Example

Input:

4

4 2 5 2

Output:

9

2 4 5 6 7 8 9 11 13

Removal Game

CSES - Removal Game

Time limit: 1.00 s
Memory limit: 512 MB

There is a list of

n

$n$ numbers and two players who move alternately. On each move, a player removes either the first or last number from the list, and their score increases by that number. Both players try to maximize their scores.

What is the maximum possible score for the first player when both players play optimally?

Input

The first input line contains an integer

n

$n$ : the size of the list.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the list.

Output

Print the maximum possible score for the first player.

Constraints

$1 \le n \le 5000$
$-10^9 \le x_i \le 10^9$

Example

Input:

4

4 5 1 3

Output:
8

Two Sets II

CSES - Two Sets II

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count the number of ways numbers

1, 2, \dots, n

$1,2,\ldots,n$ can be divided into two sets of equal sum.

For example, if

n = 7

$n=7$ , there are four solutions:

$\{1,3,4,6\}$ and $\{2,5,7\}$
$\{1,2,5,6\}$ and $\{3,4,7\}$
$\{1,2,4,7\}$ and $\{3,5,6\}$
$\{1,6,7\}$ and $\{2,3,4,5\}$

Input

The only input line contains an integer

n

$n$ .

Output

Print the answer modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 500$

Example

Input:
7

Output:
4

Increasing Subsequence

CSES - Increasing Subsequence

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array containing

n

$n$ integers. Your task is to determine the longest increasing subsequence in the array, i.e., the longest subsequence where every element is larger than the previous one.

A subsequence is a sequence that can be derived from the array by deleting some elements without changing the order of the remaining elements.

Input

The first line contains an integer

n

$n$ : the size of the array.

After this there are

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

8

7 3 5 3 6 2 9 8

Output:
4

Increasing Subsequence

CSES - Increasing Subsequence

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array containing

n

n

$n$ : the size of the array.

After this there are

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

8

7 3 5 3 6 2 9 8

Output:
4

Increasing Subsquence

CSES - Increasing Subsequence

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array containing

n

n

$n$ : the size of the array.

After this there are

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$

Example

Input:

8

7 3 5 3 6 2 9 8

Output:
4

Projects

CSES - Projects

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ projects you can attend. For each project, you know its starting and ending days and the amount of money you would get as reward. You can only attend one project during a day.

What is the maximum amount of money you can earn?

Input

The first input line contains an integer

n

$n$ : the number of projects.

After this, there are

n

$n$ lines. Each such line has three integers

a_{i}

$a_i$ ,

b_{i}

$b_i$ , and

p_{i}

$p_i$ : the starting day, the ending day, and the reward.

Output

Print one integer: the maximum amount of money you can earn.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a_i \le b_i \le 10^9$
$1 \le p_i \le 10^9$

Example

Input:

Output:
7

Elevator Rides

CSES - Elevator Rides

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ people who want to get to the top of a building which has only one elevator. You know the weight of each person and the maximum allowed weight in the elevator. What is the minimum number of elevator rides?

Input

The first input line has two integers

n

$n$ and

x

$x$ : the number of people and the maximum allowed weight in the elevator.

The second line has

n

$n$ integers

w_{1}, w_{2}, \dots, w_{n}

$w_1,w_2,\dots,w_n$ : the weight of each person.

Output

Print one integer: the minimum number of rides.

Constraints

$1 \le n \le 20$
$1 \le x \le 10^9$
$1 \le w_i \le x$

Example

Input:

4 10

4 8 6 1

Output:
2

Counting Tilings

CSES - Counting Tilings

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count the number of ways you can fill an

n \times m

$n \times m$ grid using

1 \times 2

$1 \times 2$ and

2 \times 1

$2 \times 1$ tiles.

Input

The only input line has two integers

n

$n$ and

m

$m$ .

Output

Print one integer: the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10$
$1 \le m \le 1000$

Example

Input:
4 7

Output:
781

Counting Numbers

CSES - Counting Numbers

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count the number of integers between

a

$a$ and

b

$b$ where no two adjacent digits are the same.

Input

The only input line has two integers

a

$a$ and

b

$b$ .

Output

Print one integer: the answer to the problem.

Constraints

$0 \le a \le b \le 10^{18}$

Example

Input:
123 321

Output:
171

Graph Algorithms

Counting Rooms

CSES - Counting Rooms

Time limit: 1.00 s
Memory limit: 512 MB

You are given a map of a building, and your task is to count the number of its rooms. The size of the map is

n \times m

$n \times m$ squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the height and width of the map.

Then there are

n

$n$ lines of

m

$m$ characters describing the map. Each character is either . (floor) or # (wall).

Output

Print one integer: the number of rooms.

Constraints

$1 \le n,m \le 1000$

Example

Input:

5 8

########

#..#...#

####.#.#

#..#...#

########

Output:
3

Labyrinth

CSES - Labyrinth

Time limit: 1.00 s
Memory limit: 512 MB

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the height and width of the map.

Then there are

n

$n$ lines of

m

$m$ characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

Constraints

$1 \le n,m \le 1000$

Example

Input:

5 8

########

#.A#...#

#.##.#B#

#......#

########

Output:

YES

9

LDDRRRRRU

Building Roads

CSES - Building Roads

Time limit: 1.00 s
Memory limit: 512 MB

Byteland has

n

$n$ cities, and

m

$m$ roads between them. The goal is to construct new roads so that there is a route between any two cities.

Your task is to find out the minimum number of roads required, and also determine which roads should be built.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and roads. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

After that, there are

m

$m$ lines describing the roads. Each line has two integers

a

$a$ and

b

$b$ : there is a road between those cities.

A road always connects two different cities, and there is at most one road between any two cities.

Output

First print an integer

k

$k$ : the number of required roads.

Then, print

k

$k$ lines that describe the new roads. You can print any valid solution.

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

1

2 3

Message Route

CSES - Message Route

Time limit: 1.00 s
Memory limit: 512 MB

Syrjälä's network has

n

$n$ computers and

m

$m$ connections. Your task is to find out if Uolevi can send a message to Maija, and if it is possible, what is the minimum number of computers on such a route.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of computers and connections. The computers are numbered

1, 2, \dots, n

$1,2,\dots,n$ . Uolevi's computer is

1

$1$ and Maija's computer is

n

$n$ .

Then, there are

m

$m$ lines describing the connections. Each line has two integers

a

$a$ and

b

$b$ : there is a connection between those computers.

Every connection is between two different computers, and there is at most one connection between any two computers.

Output

If it is possible to send a message, first print

k

$k$ : the minimum number of computers on a valid route. After this, print an example of such a route. You can print any valid solution.

If there are no routes, print "IMPOSSIBLE".

Constraints

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

3

1 4 5

Building Teams

CSES - Building Teams

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ pupils in Uolevi's class, and

m

$m$ friendships between them. Your task is to divide the pupils into two teams in such a way that no two pupils in a team are friends. You can freely choose the sizes of the teams.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of pupils and friendships. The pupils are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the friendships. Each line has two integers

a

$a$ and

b

$b$ : pupils

a

$a$ and

b

$b$ are friends.

Every friendship is between two different pupils. You can assume that there is at most one friendship between any two pupils.

Output

Print an example of how to build the teams. For each pupil, print "1" or "2" depending on to which team the pupil will be assigned. You can print any valid team.

If there are no solutions, print "IMPOSSIBLE".

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
1 2 2 1 2

Round Trip

CSES - Round Trip

Time limit: 1.00 s
Memory limit: 512 MB

Byteland has

n

$n$ cities and

m

$m$ roads between them. Your task is to design a round trip that begins in a city, goes through two or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and roads. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the roads. Each line has two integers

a

$a$ and

b

$b$ : there is a road between those cities.

Every road is between two different cities, and there is at most one road between any two cities.

Output

First print an integer

k

$k$ : the number of cities on the route. Then print

k

$k$ cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

4

3 5 1 3

Monsters

CSES - Monsters

Time limit: 1.00 s
Memory limit: 512 MB

You and some monsters are in a labyrinth. When taking a step to some direction in the labyrinth, each monster may simultaneously take one as well. Your goal is to reach one of the boundary squares without ever sharing a square with a monster.

Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your plan has to work in any situation; even if the monsters know your path beforehand.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the height and width of the map.

After this there are

n

$n$ lines of

m

$m$ characters describing the map. Each character is . (floor), # (wall), A (start), or M (monster). There is exactly one A in the input.

Output

First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You can print any path, as long as its length is at most

n \cdot m

$n \cdot m$ steps.

Constraints

$1 \le n,m \le 1000$

Example

Input:

5 8

########

#M..A..#

#.#.M#.#

#M#..#..

#.######

Output:

YES

5

RRDDR

Shortest Routes I

CSES - Shortest Routes I

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ cities and

m

$m$ flight connections between them. Your task is to determine the length of the shortest route from Syrjälä to every city.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and flight connections. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ , and city

1

$1$ is Syrjälä.

After that, there are

m

$m$ lines describing the flight connections. Each line has three integers

a

$a$ ,

b

$b$ and

c

$c$ : a flight begins at city

a

$a$ , ends at city

b

$b$ , and its length is

c

$c$ . Each flight is a one-way flight.

You can assume that it is possible to travel from Syrjälä to all other cities.

Output

Print

n

$n$ integers: the shortest route lengths from Syrjälä to cities

1, 2, \dots, n

$1,2,\dots,n$ .

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
0 5 2

Shortest Routes II

CSES - Shortest Routes II

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ cities and

m

$m$ roads between them. Your task is to process

q

$q$ queries where you have to determine the length of the shortest route between two given cities.

Input

The first input line has three integers

n

$n$ ,

m

$m$ and

q

$q$ : the number of cities, roads, and queries.

Then, there are

m

$m$ lines describing the roads. Each line has three integers

a

$a$ ,

b

$b$ and

c

$c$ : there is a road between cities

a

$a$ and

b

$b$ whose length is

c

$c$ . All roads are two-way roads.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ : determine the length of the shortest route between cities

a

$a$ and

b

$b$ .

Output

Print the length of the shortest route for each query. If there is no route, print

- 1

$-1$ instead.

Constraints

$1 \le n \le 500$
$1 \le m \le n^2$
$1 \le q \le 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:

High Score

CSES - High Score

Time limit: 1.00 s
Memory limit: 512 MB

You play a game consisting of

n

$n$ rooms and

m

$m$ tunnels. Your initial score is

0

$0$ , and each tunnel increases your score by

x

$x$ where

x

$x$ may be both positive or negative. You may go through a tunnel several times.

Your task is to walk from room

1

$1$ to room

n

$n$ . What is the maximum score you can get?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of rooms and tunnels. The rooms are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the tunnels. Each line has three integers

a

$a$ ,

b

$b$ and

x

$x$ : the tunnel starts at room

a

$a$ , ends at room

b

$b$ , and it increases your score by

x

$x$ . All tunnels are one-way tunnels.

You can assume that it is possible to get from room

1

$1$ to room

n

$n$ .

Output

Print one integer: the maximum score you can get. However, if you can get an arbitrarily large score, print

- 1

$-1$ .

Constraints

$1 \le n \le 2500$
$1 \le m \le 5000$
$1 \le a,b \le n$
$-10^9 \le x \le 10^9$

Example

Input:

Output:
5

Flight Discount

CSES - Flight Discount

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to find a minimum-price flight route from Syrjälä to Metsälä. You have one discount coupon, using which you can halve the price of any single flight during the route. However, you can only use the coupon once.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and flight connections. The cities are numbered

1, 2, \dots, n

$1,2,\ldots,n$ . City 1 is Syrjälä, and city

n

$n$ is Metsälä.

After this there are

m

$m$ lines describing the flights. Each line has three integers

a

$a$ ,

b

$b$ , and

c

$c$ : a flight begins at city

a

$a$ , ends at city

b

$b$ , and its price is

c

$c$ . Each flight is unidirectional.

You can assume that it is always possible to get from Syrjälä to Metsälä.

Output

Print one integer: the price of the cheapest route from Syrjälä to Metsälä.

When you use the discount coupon for a flight whose price is

x

$x$ , its price becomes

⌊ x / 2 ⌋

$\lfloor x/2 \rfloor$ (it is rounded down to an integer).

Constraints

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
2

Circle Finding

CSES - Flight Discount

Time limit: 1.00 s
Memory limit: 512 MB

n

$n$ and

m

$m$ : the number of cities and flight connections. The cities are numbered

1, 2, \dots, n

$1,2,\ldots,n$ . City 1 is Syrjälä, and city

n

$n$ is Metsälä.

After this there are

m

$m$ lines describing the flights. Each line has three integers

a

$a$ ,

b

$b$ , and

c

$c$ : a flight begins at city

a

$a$ , ends at city

b

$b$ , and its price is

c

x

$x$ , its price becomes

⌊ x / 2 ⌋

$\lfloor x/2 \rfloor$ (it is rounded down to an integer).

Constraints

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
2

Round Trip II

CSES - Round Trip II

Time limit: 1.00 s
Memory limit: 512 MB

Byteland has

n

$n$ cities and

m

$m$ flight connections. Your task is to design a round trip that begins in a city, goes through one or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and flights. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the flights. Each line has two integers

a

$a$ and

b

$b$ : there is a flight connection from city

a

$a$ to city

b

$b$ . All connections are one-way flights from a city to another city.

Output

First print an integer

k

$k$ : the number of cities on the route. Then print

k

$k$ cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

4

2 1 3 2

Course Schedule

CSES - Course Schedule

Time limit: 1.00 s
Memory limit: 512 MB

You have to complete

n

$n$ courses. There are

m

$m$ requirements of the form "course

a

$a$ has to be completed before course

b

$b$ ". Your task is to find an order in which you can complete the courses.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of courses and requirements. The courses are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

After this, there are

m

$m$ lines describing the requirements. Each line has two integers

a

$a$ and

b

$b$ : course

a

$a$ has to be completed before course

b

$b$ .

Output

Print an order in which you can complete the courses. You can print any valid order that includes all the courses.

If there are no solutions, print "IMPOSSIBLE".

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
3 4 1 5 2

LOngest Flight Route

CSES - Longest Flight Route

Time limit: 1.00 s
Memory limit: 512 MB

Uolevi has won a contest, and the prize is a free flight trip that can consist of one or more flights through cities. Of course, Uolevi wants to choose a trip that has as many cities as possible.

Uolevi wants to fly from Syrjälä to Lehmälä so that he visits the maximum number of cities. You are given the list of possible flights, and you know that there are no directed cycles in the flight network.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and flights. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ . City

1

$1$ is Syrjälä, and city

n

$n$ is Lehmälä.

After this, there are

m

$m$ lines describing the flights. Each line has two integers

a

$a$ and

b

$b$ : there is a flight from city

a

$a$ to city

b

$b$ . Each flight is a one-way flight.

Output

First print the maximum number of cities on the route. After this, print the cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

4

1 3 4 5

Game Routes

CSES - Game Routes

Time limit: 1.00 s
Memory limit: 512 MB

A game has

n

$n$ levels, connected by

m

$m$ teleporters, and your task is to get from level

1

$1$ to level

n

$n$ . The game has been designed so that there are no directed cycles in the underlying graph. In how many ways can you complete the game?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of levels and teleporters. The levels are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

After this, there are

m

$m$ lines describing the teleporters. Each line has two integers

a

$a$ and

b

$b$ : there is a teleporter from level

a

$a$ to level

b

$b$ .

Output

Print one integer: the number of ways you can complete the game. Since the result may be large, print it modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
3

Investigation

CSES - Investigation

Time limit: 1.00 s
Memory limit: 512 MB

You are going to travel from Syrjälä to Lehmälä by plane. You would like to find answers to the following questions:

what is the minimum price of such a route?
how many minimum-price routes are there? (modulo $10^9+7)$
what is the minimum number of flights in a minimum-price route?
what is the maximum number of flights in a minimum-price route?

Input

The first input line contains two integers

n

$n$ and

m

$m$ : the number of cities and the number of flights. The cities are numbered

1, 2, \dots, n

$1,2,\ldots,n$ . City 1 is Syrjälä, and city

n

$n$ is Lehmälä.

After this, there are

m

$m$ lines describing the flights. Each line has three integers

a

$a$ ,

b

$b$ , and

c

$c$ : there is a flight from city

a

$a$ to city

b

$b$ with price

c

$c$ . All flights are one-way flights.

You may assume that there is a route from Syrjälä to Lehmälä.

Output

Print four integers according to the problem statement.

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
5 2 1 2

PLanet Queries I

CSES - Planets Queries I

Time limit: 1.00 s
Memory limit: 512 MB

You are playing a game consisting of

n

$n$ planets. Each planet has a teleporter to another planet (or the planet itself).

Your task is to process

q

$q$ queries of the form: when you begin on planet

x

$x$ and travel through

k

$k$ teleporters, which planet will you reach?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of planets and queries. The planets are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

The second line has

n

$n$ integers

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\dots,t_n$ : for each planet, the destination of the teleporter. It is possible that

t_{i} = i

$t_i=i$ .

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

x

$x$ and

k

$k$ : you start on planet

x

$x$ and travel through

k

$k$ teleporters.

Output

Print the answer to each query.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le t_i \le n$
$1 \le x \le n$
$0 \le k \le 10^9$

Example

Input:

Output:

Planet Queries II

CSES - Planets Queries II

Time limit: 1.00 s
Memory limit: 512 MB

You are playing a game consisting of n planets. Each planet has a teleporter to another planet (or the planet itself).

You have to process

q

$q$ queries of the form: You are now on planet

a

$a$ and want to reach planet

b

$b$ . What is the minimum number of teleportations?

Input

The first input line contains two integers

n

$n$ and

q

$q$ : the number of planets and queries. The planets are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The second line contains

n

$n$ integers

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\ldots,t_n$ : for each planet, the destination of the teleporter.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ : you are now on planet

a

$a$ and want to reach planet

b

$b$ .

Output

For each query, print the minimum number of teleportations. If it is not possible to reach the destination, print

- 1

$-1$ .

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

Planet Cycles

CSES - Planets Cycles

Time limit: 1.00 s
Memory limit: 512 MB

You are playing a game consisting of

n

$n$ planets. Each planet has a teleporter to another planet (or the planet itself).

You start on a planet and then travel through teleporters until you reach a planet that you have already visited before.

Your task is to calculate for each planet the number of teleportations there would be if you started on that planet.

Input

The first input line has an integer

n

$n$ : the number of planets. The planets are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

The second line has

n

$n$ integers

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\dots,t_n$ : for each planet, the destination of the teleporter. It is possible that

t_{i} = i

$t_i=i$ .

Output

Print

n

$n$ integers according to the problem statement.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le t_i \le n$

Example

Input:

5

2 4 3 1 4

Output:
3 3 1 3 4

Road Reparation

CSES - Road Reparation

Time limit: 1.00 s
Memory limit: 128 MB

There are

n

$n$ cities and

m

$m$ roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and roads. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the roads. Each line has three integers

a

$a$ ,

b

$b$ and

c

$c$ : there is a road between cities

a

$a$ and

b

$b$ , and its reparation cost is

c

$c$ . All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two cities.

Output

Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
14

Road Construction

CSES - Road Construction

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of

m

$m$ roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and roads. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the new roads. Each line has two integers

a

$a$ and

b

$b$ : a new road is constructed between cities

a

$a$ and

b

$b$ .

You may assume that every road will be constructed between two different cities.

Output

Print

m

$m$ lines: the required information after each day.

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

Flight Routes Checks

CSES - Flight Routes Check

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ cities and

m

$m$ flight connections. Your task is to check if you can travel from any city to any other city using the available flights.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and flights. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

After this, there are

m

$m$ lines describing the flights. Each line has two integers

a

$a$ and

b

$b$ : there is a flight from city

a

$a$ to city

b

$b$ . All flights are one-way flights.

Output

Print "YES" if all routes are possible, and "NO" otherwise. In the latter case also print two cities

a

$a$ and

b

$b$ such that you cannot travel from city

a

$a$ to city

b

$b$ .

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

NO

4 2

Planets and Kingdoms

CSES - Planets and Kingdoms

Time limit: 1.00 s
Memory limit: 512 MB

A game has

n

$n$ planets, connected by

m

$m$ teleporters. Two planets

a

$a$ and

b

$b$ belong to the same kingdom exactly when there is a route both from

a

$a$ to

b

$b$ and from

b

$b$ to

a

$a$ . Your task is to determine for each planet its kingdom.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of planets and teleporters. The planets are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

After this, there are

m

$m$ lines describing the teleporters. Each line has two integers

a

$a$ and

b

$b$ : you can travel from planet

a

$a$ to planet

b

$b$ through a teleporter.

Output

First print an integer

k

$k$ : the number of kingdoms. After this, print for each planet a kingdom label between

1

$1$ and

k

$k$ . You can print any valid solution.

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

2

1 1 1 2 2

Giant Pizza

CSES - Giant Pizza

Time limit: 1.00 s
Memory limit: 512 MB

Uolevi's family is going to order a large pizza and eat it together. A total of

n

$n$ family members will join the order, and there are

m

$m$ possible toppings. The pizza may have any number of toppings.

Each family member gives two wishes concerning the toppings of the pizza. The wishes are of the form "topping

x

$x$ is good/bad". Your task is to choose the toppings so that at least one wish from everybody becomes true (a good topping is included in the pizza or a bad topping is not included).

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of family members and toppings. The toppings are numbered

1, 2, \dots, m

$1,2,\dots,m$ .

After this, there are

n

$n$ lines describing the wishes. Each line has two wishes of the form "+

x

$x$ " (topping

x

$x$ is good) or "-

x

$x$ " (topping

x

$x$ is bad).

Output

Print a line with

m

$m$ symbols: for each topping "+" if it is included and "-" if it is not included. You can print any valid solution.

If there are no valid solutions, print "IMPOSSIBLE".

Constraints

$1 \le n,m \le 10^5$
$1 \le x \le m$

Example

Input:

Output:
- + + + -

Coin Collector

CSES - Coin Collector

Time limit: 1.00 s
Memory limit: 512 MB

A game has

n

$n$ rooms and

m

$m$ tunnels between them. Each room has a certain number of coins. What is the maximum number of coins you can collect while moving through the tunnels when you can freely choose your starting and ending room?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of rooms and tunnels. The rooms are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

n

$n$ integers

k_{1}, k_{2}, \dots, k_{n}

$k_1,k_2,\ldots,k_n$ : the number of coins in each room.

Finally, there are

m

$m$ lines describing the tunnels. Each line has two integers

a

$a$ and

b

$b$ : there is a tunnel from room

a

$a$ to room

b

$b$ . Each tunnel is a one-way tunnel.

Output

Print one integer: the maximum number of coins you can collect.

Constraints

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le k_i \le 10^9$
$1 \le a,b \le n$

Example

Input:

Output:
16

Mail Delivery

CSES - Mail Delivery

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of crossings and streets. The crossings are numbered

1, 2, \dots, n

$1,\,2,\ldots,\,n$ , and the post office is located at crossing

1

$1$ .

After that, there are m lines describing the streets. Each line has two integers

a

$a$ and

b

$b$ : there is a street between crossings

a

$a$ and

b

$b$ . All streets are two-way streets.

Every street is between two different crossings, and there is at most one street between two crossings.

Output

Print all the crossings on the route in the order you will visit them. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

2 \leq n \leq 10^{5}

$2\leq n\leq 10^5$

1 \leq m \leq 2 . 10^{5}

$1\leq m\leq 2 . 10^5$

1 \leq a, b \leq n

$1\leq a,\,b\leq n$

Example

Input:

Output:
1 2 6 3 2 4 5 3 1

De Bruijn Sequence

CSES - De Bruijn Sequence

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to construct a minimum-length bit string that contains all possible substrings of length

n

$n$ . For example, when

n = 2

$n=2$ , the string 00110 is a valid solution, because its substrings of length

2

$2$ are 00, 01, 10 and 11.

Input

The only input line has an integer

n

$n$ .

Output

Print a minimum-length bit string that contains all substrings of length

n

$n$ . You can print any valid solution.

Constraints

$1 \le n \le 15$

Example

Input:
2

Output:
00110

Teleporters Path

CSES - Teleporters Path

Time limit: 1.00 s
Memory limit: 512 MB

A game has

n

$n$ levels and

m

$m$ teleportes between them. You win the game if you move from level

1

$1$ to level

n

$n$ using every teleporter exactly once.

Can you win the game, and what is a possible way to do it?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of levels and teleporters. The levels are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the teleporters. Each line has two integers

a

$a$ and

b

$b$ : there is a teleporter from level

a

$a$ to level

b

$b$ .

You can assume that each pair

(a, b)

$(a,b)$ in the input is distinct.

Output

Print

m + 1

$m+1$ integers: the sequence in which you visit the levels during the game. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
1 3 1 2 4 2 5

Hamiltonian Flights

CSES - Hamiltonian Flights

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ cities and

m

$m$ flight connections between them. You want to travel from Syrjälä to Lehmälä so that you visit each city exactly once. How many possible routes are there?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of cities and flights. The cities are numbered

1, 2, \dots, n

$1,2,\dots,n$ . City

1

$1$ is Syrjälä, and city

n

$n$ is Lehmälä.

Then, there are

m

$m$ lines describing the flights. Each line has two integers

a

$a$ and

b

$b$ : there is a flight from city

a

$a$ to city

b

$b$ . All flights are one-way flights.

Output

Print one integer: the number of routes modulo

10^{9} + 7

$10^9+7$ .

Constraints

$2 \le n \le 20$
$1 \le m \le n^2$
$1 \le a,b \le n$

Example

Input:

Output:
2

Knight's Tour

CSES - Knight's Tour

Time limit: 1.00 s
Memory limit: 512 MB

Given a starting position of a knight on an

8 \times 8

$8 \times 8$ chessboard, your task is to find a sequence of moves such that it visits every square exactly once.

On each move, the knight may either move two steps horizontally and one step vertically, or one step horizontally and two steps vertically.

Input

The only line has two integers

x

$x$ and

y

$y$ : the knight's starting position.

Output

Print a grid that shows how the knight moves (according to the example). You can print any valid solution.

Constraints

$1 \le x,y \le 8$

Example

Input:
2 1

Output:

8 1 10 13 6 3 20 17 

11 14 7 2 19 16 23 4 

26 9 12 15 24 5 18 21 

49 58 25 28 51 22 33 30 

40 27 50 59 32 29 52 35 

57 48 41 44 37 34 31 62 

42 39 46 55 60 63 36 53 

47 56 43 38 45 54 61 64

Download Speed

CSES - Download Speed

Time limit: 1.00 s
Memory limit: 512 MB

Consider a network consisting of

n

$n$ computers and

m

$m$ connections. Each connection specifies how fast a computer can send data to another computer.

Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of computers and connections. The computers are numbered

1, 2, \dots, n

$1,2,\dots,n$ . Computer

1

$1$ is the server and computer

n

$n$ is Kotivalo's computer.

After this, there are

m

$m$ lines describing the connections. Each line has three integers

a

$a$ ,

b

$b$ and

c

$c$ : computer

a

$a$ can send data to computer

b

$b$ at speed

c

$c$ .

Output

Print one integer: the maximum speed Kotivalo can download data.

Constraints

$1 \le n \le 500$
$1 \le m \le 1000$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
6

Police Chase

CSES - Download Speed

Time limit: 1.00 s
Memory limit: 512 MB

Consider a network consisting of

n

$n$ computers and

m

n

$n$ and

m

$m$ : the number of computers and connections. The computers are numbered

1, 2, \dots, n

$1,2,\dots,n$ . Computer

1

$1$ is the server and computer

n

$n$ is Kotivalo's computer.

After this, there are

m

$m$ lines describing the connections. Each line has three integers

a

$a$ ,

b

$b$ and

c

$c$ : computer

a

$a$ can send data to computer

b

$b$ at speed

c

$c$ .

Output

Print one integer: the maximum speed Kotivalo can download data.

Constraints

$1 \le n \le 500$
$1 \le m \le 1000$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
6

School Dance

CSES - School Dance

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ boys and

m

$m$ girls in a school. Next week a school dance will be organized. A dance pair consists of a boy and a girl, and there are

k

$k$ potential pairs.

Your task is to find out the maximum number of dance pairs and show how this number can be achieved.

Input

The first input line has three integers

n

$n$ ,

m

$m$ and

k

$k$ : the number of boys, girls, and potential pairs. The boys are numbered

1, 2, \dots, n

$1,2,\dots,n$ , and the girls are numbered

1, 2, \dots, m

$1,2,\dots,m$ .

After this, there are

k

$k$ lines describing the potential pairs. Each line has two integers

a

$a$ and

b

$b$ : boy

a

$a$ and girl

b

$b$ are willing to dance together.

Output

First print one integer

r

$r$ : the maximum number of dance pairs. After this, print

r

$r$ lines describing the pairs. You can print any valid solution.

Constraints

$1 \le n,m \le 500$
$1 \le k \le 1000$
$1 \le a \le n$
$1 \le b \le m$

Example

Input:

Output:

Distinct Routes

CSES - Distinct Routes

Time limit: 1.00 s
Memory limit: 512 MB

A game consists of

n

$n$ rooms and

m

$m$ teleporters. At the beginning of each day, you start in room

1

$1$ and you have to reach room

n

$n$ .

You can use each teleporter at most once during the game. How many days can you play if you choose your routes optimally?

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of rooms and teleporters. The rooms are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

After this, there are

m

$m$ lines describing the teleporters. Each line has two integers

a

$a$ and

b

$b$ : there is a teleporter from room

a

$a$ to room

b

$b$ .

There are no two teleporters whose starting and ending room are the same.

Output

First print an integer

k

$k$ : the maximum number of days you can play the game. Then, print

k

$k$ route descriptions according to the example. You can print any valid solution.

Constraints

$2 \le n \le 500$
$1 \le m \le 1000$
$1 \le a,b \le n$

Example

Input:

Output:

Static Range Sum Queries

CSES - Static Range Sum Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the form: what is the sum of values in range

[a, b]

$[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ : what is the sum of values in range

[a, b]

$[a,b]$ ?

Output

Print the result of each query.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
$1 \le a \le b \le n$

Example

Input:

8 4

3 2 4 5 1 1 5 3

2 4

5 6

1 8

3 3

Output:

Static Range Minimum Queries

CSES - Static Range Minimum Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the form: what is the minimum value in range

[a, b]

$[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ : what is the minimum value in range

[a, b]

$[a,b]$ ?

Output

Print the result of each query.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
$1 \le a \le b \le n$

Example

Input:

8 4

3 2 4 5 1 1 5 3

2 4

5 6

1 8

3 3

Output:

Dynamic Range Sum Queries

CSES - Dynamic Range Sum Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the following types:

update the value at position $k$ to $u$
what is the sum of values in range $[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has three integers: either "

1

$1$

k

$k$

u

$u$ " or "

2

$2$

a

$a$

b

$b$ ".

Output

Print the result of each query of type 2.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i, u \le 10^9$
$1 \le k \le n$
$1 \le a \le b \le n$

Example

Input:

8 4

3 2 4 5 1 1 5 3

2 1 4

2 5 6

1 3 1

2 1 4

Output:

Dynamic Range Minimum Queries

CSES - Dynamic Range Minimum Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the following types:

update the value at position $k$ to $u$
what is the minimum value in range $[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has three integers: either "

1

$1$

k

$k$

u

$u$ " or "

2

$2$

a

$a$

b

$b$ ".

Output

Print the result of each query of type 2.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i, u \le 10^9$
$1 \le k \le n$
$1 \le a \le b \le n$

Example

Input:

8 4

3 2 4 5 1 1 5 3

2 1 4

2 5 6

1 2 3

2 1 4

Output:

Range Xor Queries

CSES - Range Xor Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the form: what is the xor sum of values in range

[a, b]

$[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ : what is the xor sum of values in range

[a, b]

$[a,b]$ ?

Output

Print the result of each query.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
$1 \le a \le b \le n$

Example

Input:

8 4

3 2 4 5 1 1 5 3

2 4

5 6

1 8

3 3

Output:

Range Update Queries

CSES - Range Update Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the following types:

increase each value in range $[a,b]$ by $u$
what is the value at position $k$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has three integers: either "

1

$1$

a

$a$

b

$b$

u

$u$ " or "

2

$2$

k

$k$ ".

Output

Print the result of each query of type 2.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i, u \le 10^9$
$1 \le k \le n$
$1 \le a \le b \le n$

Example

Input:

8 3

3 2 4 5 1 1 5 3

2 4

1 2 5 1

2 4

Output:

5

6

Forest Queries

CSES - Forest Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given an

n \times n

$n \times n$ grid representing the map of a forest. Each square is either empty or contains a tree. The upper-left square has coordinates

(1, 1)

$(1,1)$ , and the lower-right square has coordinates

(n, n)

$(n,n)$ .

Your task is to process

q

$q$ queries of the form: how many trees are inside a given rectangle in the forest?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the size of the forest and the number of queries.

Then, there are

n

$n$ lines describing the forest. Each line has

n

$n$ characters: . is an empty square and * is a tree.

Finally, there are

q

$q$ lines describing the queries. Each line has four integers

y_{1}

$y_1$ ,

x_{1}

$x_1$ ,

y_{2}

$y_2$ ,

x_{2}

$x_2$ corresponding to the corners of a rectangle.

Output

Print the number of trees inside each rectangle.

Constraints

$1 \le n \le 1000$
$1 \le q \le 2 \cdot 10^5$
$1 \le y_1 \le y_2 \le n$
$1 \le x_1 \le x_2 \le n$

Example

Input:

4 3

.*..

*.**

**..

****

2 2 3 4

3 1 3 1

1 1 2 2

Output:

Hotel Queries

CSES - Hotel Queries

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ hotels on a street. For each hotel you know the number of free rooms. Your task is to assign hotel rooms for groups of tourists. All members of a group want to stay in the same hotel.

The groups will come to you one after another, and you know for each group the number of rooms it requires. You always assign a group to the first hotel having enough rooms. After this, the number of free rooms in the hotel decreases.

Input

The first input line contains two integers

n

$n$ and

m

$m$ : the number of hotels and the number of groups. The hotels are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line contains

n

$n$ integers

h_{1}, h_{2}, \dots, h_{n}

$h_1,h_2,\ldots,h_n$ : the number of free rooms in each hotel.

The last line contains

m

$m$ integers

r_{1}, r_{2}, \dots, r_{m}

$r_1,r_2,\ldots,r_m$ : the number of rooms each group requires.

Output

Print the assigned hotel for each group. If a group cannot be assigned a hotel, print 0 instead.

Constraints

$1 \le n,m \le 2 \cdot 10^5$
$1 \le h_i \le 10^9$
$1 \le r_i \le 10^9$

Example

Input:

8 5

3 2 4 1 5 5 2 6

4 4 7 1 1

Output:
3 5 0 1 1

List Removals

CSES - List Removals

Time limit: 1.00 s
Memory limit: 512 MB

You are given a list consisting of

n

$n$ integers. Your task is to remove elements from the list at given positions, and report the removed elements.

Input

The first input line has an integer

n

$n$ : the initial size of the list. During the process, the elements are numbered

1, 2, \dots, k

$1,2,\dots,k$ where

k

$k$ is the current size of the list.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the contents of the list.

The last line has

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\dots,p_n$ : the positions of the elements to be removed.

Output

Print the elements in the order they are removed.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
$1 \le p_i \le n-i+1$

Example

Input:

Output:
1 2 2 6 4

Explanation: The contents of the list are

[2, 6, 1, 4, 2]

$[2,6,1,4,2]$ ,

[2, 6, 4, 2]

$[2,6,4,2]$ ,

[6, 4, 2]

$[6,4,2]$ ,

[6, 4]

$[6,4]$ ,

[4]

$[4]$ and

[]

$[]$ .

Salary Queries

CSES - Salary Queries

Time limit: 1.00 s
Memory limit: 512 MB

A company has

n

$n$ employees with certain salaries. Your task is to keep track of the salaries and process queries.

Input

The first input line contains two integers

n

$n$ and

q

$q$ : the number of employees and queries. The employees are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line has

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\ldots,p_n$ : each employee's salary.

After this, there are

q

$q$ lines describing the queries. Each line has one of the following forms:

! $k$ $x$ : change the salary of employee $k$ to $x$
? $a$ $b$ : count the number of employees whose salary is between $a \ldots b$

Output

Print the answer to each ? query.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le p_i \le 10^9$
$1 \le k \le n$
$1 \le x \le 10^9$
$1 \le a \le b \le 10^9$

Example

Input:

Output:

3

2

Prefix Sum Queries

CSES - Prefix Sum Queries

Time limit: 1.00 s
Memory limit: 512 MB

Given an array of

n

$n$ integers, your task is to process

q

$q$ queries of the following types:

update the value at position $k$ to $u$
what is the maximum prefix sum in range $[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of values and queries.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has three integers: either "

1

$1$

k

$k$

u

$u$ " or "

2

$2$

a

$a$

b

$b$ ".

Output

Print the result of each query of type 2.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$-10^9 \le x_i, u \le 10^9$
$1 \le k \le n$
$1 \le a \le b \le n$

Example

Input:

8 4

1 2 -1 3 1 -5 1 4

2 2 6

1 4 -2

2 2 6

2 3 4

Output:

Pizzeria Queries

CSES - Pizzeria Queries

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ buildings on a street, numbered

1, 2, \dots, n

$1,2,\dots,n$ . Each building has a pizzeria and an apartment.

The pizza price in building

k

$k$ is

p_{k}

$p_k$ . If you order a pizza from building

a

$a$ to building

b

$b$ , its price (with delivery) is

p_{a} + | a - b |

$p_a+|a-b|$ .

Your task is to process two types of queries:

The pizza price $p_k$ in building $k$ becomes $x$ .
You are in building $k$ and want to order a pizza. What is the minimum price?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of buildings and queries.

The second line has

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\dots,p_n$ : the initial pizza price in each building.

Finally, there are

q

$q$ lines that describe the queries. Each line is either "1

k

$k$

x

$x$ " or "2

k

$k$ ".

Output

Print the answer for each query of type 2.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le p_i, x \le 10^9$
$1 \le k \le n$

Example

Input:

6 3

8 6 4 5 7 5

2 2

1 5 1

2 2

Output:

5

4

Subarray Sum Queries

CSES - Subarray Sum Queries

Time limit: 1.00 s
Memory limit: 512 MB

There is an array consisting of

n

$n$ integers. Some values of the array will be updated, and after each update, your task is to report the maximum subarray sum in the array.

Input

The first input line contains integers

n

$n$ and

m

$m$ : the size of the array and the number of updates. The array is indexed

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line has

n

$n$ integers:

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the initial contents of the array.

Then there are

m

$m$ lines describing the changes. Each line has two integers

k

$k$ and

x

$x$ : the value at position

k

$k$ becomes

x

$x$ .

Output

After each update, print the maximum subarray sum. Empty subarrays (with sum

0

$0$ ) are allowed.

Constraints

$1 \le n, m \le 2 \cdot 10^5$
$-10^9 \le x_i \le 10^9$
$1 \le k \le n$
$-10^9 \le x \le 10^9$

Example

Input:

5 3

1 2 -3 5 -1

2 6

3 1

2 -2

Output:

Distinct Values Queries

CSES - Distinct Values Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ integers and

q

$q$ queries of the form: how many distinct values are there in a range

[a, b]

$[a,b]$ ?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the array size and number of queries.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the array values.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ .

Output

For each query, print the number of distinct values in the range.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
$1 \le a \le b \le n$

Example

Input:

Output:

Increasing Array Queries

CSES - Increasing Array Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array that consists of

n

$n$ integers. The array elements are indexed

1, 2, \dots, n

$1,2,\dots,n$ .

You can modify the array using the following operation: choose an array element and increase its value by one.

Your task is to process

q

$q$ queries of the form: when we consider a subarray from position

a

$a$ to position

b

$b$ , what is the minimum number of operations after which the subarray is increasing?

An array is increasing if each element is greater than or equal with the previous element.

Input

The first input line has two integers

n

$n$ and

q

$q$ : the size of the array and the number of queries.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the contents of the array.

Finally, there are

q

$q$ lines that describe the queries. Each line has two integers

a

$a$ and

b

$b$ : the starting and ending position of a subarray.

Output

For each query, print the minimum number of operations.

Constraints

$1 \le n,q \le 2\cdot10^5$
$1 \le x_i \le 10^9$
$1 \le a \le b \le n$

Example

Input:

Output:

Forest Queries II

CSES - Forest Queries II

Time limit: 1.00 s
Memory limit: 512 MB

You are given an

n \times n

$n \times n$ grid representing the map of a forest. Each square is either empty or has a tree. Your task is to process

q

$q$ queries of the following types:

Change the state (empty/tree) of a square.
How many trees are inside a rectangle in the forest?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the size of the forest and the number of queries.

Then, there are

n

$n$ lines describing the forest. Each line has

n

$n$ characters: . is an empty square and * is a tree.

Finally, there are

q

$q$ lines describing the queries. The format of each line is either "

1

$1$

y

$y$

x

$x$ " or "2

y_{1}

$y_1$

x_{1}

$x_1$

y_{2}

$y_2$

x_{2}

$x_2$ ".

Output

Print the answer to each query of the second type.

Constraints

$1 \le n \le 1000$
$1 \le q \le 2 \cdot 10^5$
$1 \le y,x \le n$
$1 \le y_1 \le y_2 \le n$
$1 \le x_1 \le x_2 \le n$

Example

Input:

4 3

.*..

*.**

**..

****

2 2 2 3 4

1 3 3

2 2 2 3 4

Output:

3

4

Range Updates and Sums

CSES - Range Updates and Sums

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to maintain an array of

n

$n$ values and efficiently process the following types of queries:

Increase each value in range $[a,b]$ by $x$ .
Set each value in range $[a,b]$ to $x$ .
Calculate the sum of values in range $[a,b]$ .

Input

The first input line has two integers

n

$n$ and

q

$q$ : the array size and the number of queries.

The next line has

n

$n$ values

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\dots,t_n$ : the initial contents of the array.

Finally, there are

q

$q$ lines describing the queries. The format of each line is one of the following: "1

a

$a$

b

$b$

x

$x$ ", "2

a

$a$

b

$b$

x

$x$ ", or "3

a

$a$

b

$b$ ".

Output

Print the answer to each sum query.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le t_i, x \le 10^6$
$1 \le a \le b \le n$

Example

Input:

6 5

2 3 1 1 5 3

3 3 5

1 2 4 2

3 3 5

2 2 4 5

3 3 5

Output:

Polynomial Queries

CSES - Polynomial Queries

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to maintain an array of

n

$n$ values and efficiently process the following types of queries:

Increase the first value in range $[a,b]$ by $1$ , the second value by $2$ , the third value by $3$ , and so on.
Calculate the sum of values in range $[a,b]$ .

Input

The first input line has two integers

n

$n$ and

q

$q$ : the size of the array and the number of queries.

The next line has

n

$n$ values

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\dots,t_n$ : the initial contents of the array.

Finally, there are

q

$q$ lines describing the queries. The format of each line is either "1

a

$a$

b

$b$ " or "2

a

$a$

b

$b$ ".

Output

Print the answer to each sum query.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le t_i \le 10^6$
$1 \le a \le b \le n$

Example

Input:

Output:

17

32

Range Queries and Copies

CSES - Range Queries and Copies

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to maintain a list of arrays which initially has a single array. You have to process the following types of queries:

Set the value $a$ in array $k$ to $x$ .
Calculate the sum of values in range $[a,b]$ in array $k$ .
Create a copy of array $k$ and add it to the end of the list.

Input

The first input line has two integers

n

$n$ and

q

$q$ : the array size and the number of queries.

The next line has

n

$n$ integers

t_{1}, t_{2}, \dots, t_{n}

$t_1,t_2,\ldots,t_n$ : the initial contents of the array.

Finally, there are

q

$q$ lines describing the queries. The format of each line is one of the following: "1

k

$k$

a

$a$

x

$x$ ", "2

k

$k$

a

$a$

b

$b$ " or "3

k

$k$ ".

Output

Print the answer to each sum query.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le t_i, x \le 10^9$
$1 \le a \le b \le n$

Example

Input:

Output:

Tree Algorithms

Subordinates

CSES - Subordinates

Time limit: 1.00 s
Memory limit: 512 MB

Given the structure of a company, your task is to calculate for each employee the number of their subordinates.

Input

The first input line has an integer

n

$n$ : the number of employees. The employees are numbered

1, 2, \dots, n

$1,2,\dots,n$ , and employee

1

$1$ is the general director of the company.

After this, there are

n - 1

$n-1$ integers: for each employee

2, 3, \dots, n

$2,3,\dots,n$ their direct boss in the company.

Output

Print

n

$n$ integers: for each employee

1, 2, \dots, n

$1,2,\dots,n$ the number of their subordinates.

Constraints

$1 \le n \le 2 \cdot 10^5$

Example

Input:

5

1 1 2 3

Output:
4 1 1 0 0

CSES - Tree Matching

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes.

A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching?

Input

The first input line contains an integer

n

$n$ : the number of nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print one integer: the maximum number of pairs.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
2

Explanation: One possible matching is

(1, 2)

$(1,2)$ and

(3, 4)

$(3,4)$ .

Tree Diameter

CSES - Tree Diameter

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes.

The diameter of a tree is the maximum distance between two nodes. Your task is to determine the diameter of the tree.

Input

The first input line contains an integer

n

$n$ : the number of nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print one integer: the diameter of the tree.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
3

Explanation: The diameter corresponds to the path

2 \to 1 \to 3 \to 5

$2 \rightarrow 1 \rightarrow 3 \rightarrow 5$ .

Tree Distances I

CSES - Tree Distances I

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes.

Your task is to determine for each node the maximum distance to another node.

Input

The first input line contains an integer

n

$n$ : the number of nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print

n

$n$ integers: for each node

1, 2, \dots, n

$1,2,\ldots,n$ , the maximum distance to another node.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
2 3 2 3 3

Tree Distances II

CSES - Tree Distances II

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes.

Your task is to determine for each node the sum of the distances from the node to all other nodes.

Input

The first input line contains an integer

n

$n$ : the number of nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print

n

$n$ integers: for each node

1, 2, \dots, n

$1,2,\ldots,n$ , the sum of the distances.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
6 9 5 8 8

Company Queries I

CSES - Company Queries I

Time limit: 1.00 s
Memory limit: 512 MB

A company has

n

$n$ employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process

q

$q$ queries of the form: who is employee

x

$x$ 's boss

k

$k$ levels higher up in the hierarchy?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of employees and queries. The employees are numbered

1, 2, \dots, n

$1,2,\dots,n$ , and employee

1

$1$ is the general director.

The next line has

n - 1

$n-1$ integers

e_{2}, e_{3}, \dots, e_{n}

$e_2,e_3,\dots,e_n$ : for each employee

2, 3, \dots, n

$2,3,\dots,n$ their boss.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

x

$x$ and

k

$k$ : who is employee

x

$x$ 's boss

k

$k$ levels higher up?

Output

Print the answer for each query. If such a boss does not exist, print

- 1

$-1$ .

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le e_i \le i-1$
$1 \le x \le n$
$1 \le k \le n$

Example

Input:

Output:

Company Queries I

CSES - Company Queries I

Time limit: 1.00 s
Memory limit: 512 MB

A company has

n

$n$ employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process

q

$q$ queries of the form: who is employee

x

$x$ 's boss

k

$k$ levels higher up in the hierarchy?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of employees and queries. The employees are numbered

1, 2, \dots, n

$1,2,\dots,n$ , and employee

1

$1$ is the general director.

The next line has

n - 1

$n-1$ integers

e_{2}, e_{3}, \dots, e_{n}

$e_2,e_3,\dots,e_n$ : for each employee

2, 3, \dots, n

$2,3,\dots,n$ their boss.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

x

$x$ and

k

$k$ : who is employee

x

$x$ 's boss

k

$k$ levels higher up?

Output

Print the answer for each query. If such a boss does not exist, print

- 1

$-1$ .

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le e_i \le i-1$
$1 \le x \le n$
$1 \le k \le n$

Example

Input:

Output:

Company Queries II

CSES - Company Queries II

Time limit: 1.00 s
Memory limit: 512 MB

A company has

n

$n$ employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process

q

$q$ queries of the form: who is the lowest common boss of employees

a

$a$ and

b

$b$ in the hierarchy?

Input

The first input line has two integers

n

$n$ and

q

$q$ : the number of employees and queries. The employees are numbered

1, 2, \dots, n

$1,2,\dots,n$ , and employee

1

$1$ is the general director.

The next line has

n - 1

$n-1$ integers

e_{2}, e_{3}, \dots, e_{n}

$e_2,e_3,\dots,e_n$ : for each employee

2, 3, \dots, n

$2,3,\dots,n$ their boss.

Finally, there are

q

$q$ lines describing the queries. Each line has two integers

a

$a$ and

b

$b$ : who is the lowest common boss of employees

a

$a$ and

b

$b$ ?

Output

Print the answer for each query.

Constraints

$1 \le n,q \le 2 \cdot 10^5$
$1 \le e_i \le i-1$
$1 \le a,b \le n$

Example

Input:

Output:

Distance Queries

CSES - Distance Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes.

Your task is to process

q

$q$ queries of the form: what is the distance between nodes

a

$a$ and

b

$b$ ?

Input

The first input line contains two integers

n

$n$ and

q

$q$ : the number of nodes and queries. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Finally, there are

q

$q$ lines describing the queries. Each line contains two integer

a

$a$ and

b

$b$ : what is the distance between nodes

a

$a$ and

b

$b$ ?

Output

Print

q

$q$ integers: the answer to each query.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:

Counting Paths

CSES - Counting Paths

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes, and

m

$m$ paths in the tree.

Your task is to calculate for each node the number of paths containing that node.

Input

The first input line contains integers

n

$n$ and

m

$m$ : the number of nodes and paths. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Finally, there are

m

$m$ lines describing the paths. Each line contains two integers

a

$a$ and

b

$b$ : there is a path between nodes

a

$a$ and

b

$b$ .

Output

Print

n

$n$ integers: for each node

1, 2, \dots, n

$1,2,\ldots,n$ , the number of paths containing that node.

Constraints

$1 \le n, m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
3 1 3 1 1

Subtree Queries

CSES - Subtree Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given a rooted tree consisting of

n

$n$ nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ , and node

1

$1$ is the root. Each node has a value.

Your task is to process following types of queries:

change the value of node $s$ to $x$
calculate the sum of values in the subtree of node $s$

Input

The first input line contains two integers

n

$n$ and

q

$q$ : the number of nodes and queries. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line has

n

$n$ integers

v_{1}, v_{2}, \dots, v_{n}

$v_1,v_2,\ldots,v_n$ : the value of each node.

Then there are

n - 1

$n-1$ lines describing the edges. Each line contans two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Finally, there are

q

$q$ lines describing the queries. Each query is either of the form "1

s

$s$

x

$x$ " or "2

s

$s$ ".

Output

Print the answer to each query of type 2.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le a,b, s \le n$
$1 \le v_i, x \le 10^9$

Example

Input:

Output:

8

10

Path Queries

CSES - Path Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given a rooted tree consisting of

n

$n$ nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ , and node

1

$1$ is the root. Each node has a value.

Your task is to process following types of queries:

change the value of node $s$ to $x$
calculate the sum of values on the path from the root to node $s$

Input

The first input line contains two integers

n

$n$ and

q

$q$ : the number of nodes and queries. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line has

n

$n$ integers

v_{1}, v_{2}, \dots, v_{n}

$v_1,v_2,\ldots,v_n$ : the value of each node.

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Finally, there are

q

$q$ lines describing the queries. Each query is either of the form "1

s

$s$

x

$x$ " or "2

s

$s$ ".

Output

Print the answer to each query of type 2.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le a,b, s \le n$
$1 \le v_i, x \le 10^9$

Example

Input:

Output:

11

8

Path Queries II

CSES - Path Queries II

Time limit: 1.00 s
Memory limit: 512 MB

You are given a tree consisting of

n

$n$ nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ . Each node has a value.

Your task is to process following types of queries:

change the value of node $s$ to $x$
find the maximum value on the path between nodes $a$ and $b$ .

Input

The first input line contains two integers

n

$n$ and

q

$q$ : the number of nodes and queries. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line has

n

$n$ integers

v_{1}, v_{2}, \dots, v_{n}

$v_1,v_2,\ldots,v_n$ : the value of each node.

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Finally, there are

q

$q$ lines describing the queries. Each query is either of the form "1

s

$s$

x

$x$ " or "2

a

$a$

b

$b$ ".

Output

Print the answer to each query of type 2.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le a,b, s \le n$
$1 \le v_i, x \le 10^9$

Example

Input:

Output:
4 3

Distinct Colors

CSES - Distinct Colors

Time limit: 1.00 s
Memory limit: 512 MB

You are given a rooted tree consisting of

n

$n$ nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ , and node

1

$1$ is the root. Each node has a color.

Your task is to determine for each node the number of distinct colors in the subtree of the node.

Input

The first input line contains an integer

n

$n$ : the number of nodes. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

The next line consists of

n

$n$ integers

c_{1}, c_{2}, \dots, c_{n}

$c_1,c_2,\ldots,c_n$ : the color of each node.

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print

n

$n$ integers: for each node

1, 2, \dots, n

$1,2,\ldots,n$ , the number of distinct colors.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c_i \le 10^9$

Example

Input:

Output:
3 1 2 1 1

Finding a Centroid

CSES - Finding a Centroid

Time limit: 1.00 s
Memory limit: 512 MB

Given a tree of

n

$n$ nodes, your task is to find a centroid, i.e., a node such that when it is appointed the root of the tree, each subtree has at most

⌊ n / 2 ⌋

$\lfloor n/2 \rfloor$ nodes.

Input

The first input line contains an integer

n

$n$ : the number of nodes. The nodes are numbered

1, 2, \dots, n

$1,2,…,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print one integer: a centroid node. If there are several possibilities, you can choose any of them.

Constraints

$1 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
3

Fixed-Length Paths I

CSES - Fixed-Length Paths I

Time limit: 1.00 s
Memory limit: 512 MB

Given a tree of

n

$n$ nodes, your task is to count the number of distinct paths that consist of exactly

k

$k$ edges.

Input

The first input line contains two integers

n

$n$ and

k

$k$ : the number of nodes and the path length. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print one integer: the number of paths.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
4

Fixed-Length Paths II

CSES - Fixed-Length Paths II

Time limit: 1.00 s
Memory limit: 512 MB

Given a tree of

n

$n$ nodes, your task is to count the number of distinct paths that have at least

k_{1}

$k_1$ and at most

k_{2}

$k_2$ edges.

Input

The first input line contains three integers

n

$n$ ,

k_{1}

$k_1$ and

k_{2}

$k_2$ : the number of nodes and the path lengths. The nodes are numbered

1, 2, \dots, n

$1,2,\ldots,n$ .

Then there are

n - 1

$n-1$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge between nodes

a

$a$ and

b

$b$ .

Output

Print one integer: the number of paths.

Constraints

$1 \le k_1 \le k_2 \le n \le 2 \cdot 10^5$
$1 \le a,b \le n$

Example

Input:

Output:
6

Mathematics

Josephus Queries

CSES - Josephus Queries

Time limit: 1.00 s
Memory limit: 512 MB

Consider a game where there are

n

$n$ children (numbered

1, 2, \dots, n

$1,2,\dots,n$ ) in a circle. During the game, every second child is removed from the circle, until there are no children left.

Your task is to process

q

$q$ queries of the form: "when there are

n

$n$ children, who is the

k

$k$ th child that will be removed?"

Input

The first input line has an integer

q

$q$ : the number of queries.

After this, there are

q

$q$ lines that describe the queries. Each line has two integers

n

$n$ and

k

$k$ : the number of children and the position of the child.

Output

Print

q

$q$ integers: the answer for each query.

Constraints

$1 \le q \le 10^5$
$1 \le k \le n \le 10^9$

Example

Input:

Output:

Exponentiation

CSES - Exponentiation

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to efficiently calculate values

a^{b}

$a^b$ modulo

10^{9} + 7

$10^9+7$ .

Note that in this task we assume that

0^{0} = 1

$0^0=1$ .

Input

The first input line contains an integer

n

$n$ : the number of calculations.

After this, there are

n

$n$ lines, each containing two integers

a

$a$ and

b

$b$ .

Output

Print each value

a^{b}

$a^b$ modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 2 \cdot 10^5$
$0 \le a,b \le 10^9$

Example

Input:

Output:

Exponentiation II

CSES - Exponentiation II

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to efficiently calculate values

a^{b^{c}}

$a^{b^c}$ modulo

10^{9} + 7

$10^9+7$ .

Note that in this task we assume that

0^{0} = 1

$0^0=1$ .

Input

The first input line has an integer

n

$n$ : the number of calculations.

Afther this, there are

n

$n$ lines, each containing three integers

a

$a$ ,

b

$b$ and

c

$c$ .

Output

Print each value

a^{b^{c}}

$a^{b^c}$ modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^5$
$0 \le a,b,c \le 10^9$

Example

Input:

Output:

Counting Divisors

CSES - Counting Divisors

Time limit: 1.00 s
Memory limit: 512 MB

Given

n

$n$ integers, your task is to report for each integer the number of its divisors.

For example, if

x = 18

$x=18$ , the correct answer is

6

$6$ because its divisors are

1, 2, 3, 6, 9, 18

$1,2,3,6,9,18$ .

Input

The first input line has an integer

n

$n$ : the number of integers.

After this, there are

n

$n$ lines, each containing an integer

x

$x$ .

Output

For each integer, print the number of its divisors.

Constraints

$1 \le n \le 10^5$
$1 \le x \le 10^6$

Example

Input:

Output:

Common Divisors

CSES - Common Divisors

Time limit: 1.00 s
Memory limit: 512 MB

You are given an array of

n

$n$ positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.

Input

The first input line has an integer

n

$n$ : the size of the array.

The second line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the contents of the array.

Output

Print the maximum greatest common divisor.

Constraints

$2 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^6$

Example

Input:

5

3 14 15 7 9

Output:
7

Sum of Divisors

CSES - Sum of Divisors

Time limit: 1.00 s
Memory limit: 512 MB

Let

σ (n)

$\sigma(n)$ denote the sum of divisors of an integer

n

$n$ . For example,

σ (12) = 1 + 2 + 3 + 4 + 6 + 12 = 28

$\sigma(12)=1+2+3+4+6+12=28$ .

Your task is to calculate the sum

\sum_{i = 1}^{n} σ (i)

$\sum_{i=1}^n \sigma(i)$ modulo

10^{9} + 7

$10^9+7$ .

Input

The only input line has an integer

n

$n$ .

Output

Print

\sum_{i = 1}^{n} σ (i)

$\sum_{i=1}^n \sigma(i)$ modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^{12}$

Example

Input:
5

Output:
21

Divisor Analysis

CSES - Divisor Analysis

Time limit: 1.00 s
Memory limit: 512 MB

Given an integer, your task is to find the number, sum and product of its divisors. As an example, let us consider the number

12

$12$ :

the number of divisors is $6$ (they are $1$ , $2$ , $3$ , $4$ , $6$ , $12$ )
the sum of divisors is $1+2+3+4+6+12=28$
the product of divisors is $1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728$

Since the input number may be large, it is given as a prime factorization.

Input

The first line has an integer

n

$n$ : the number of parts in the prime factorization.

After this, there are

n

$n$ lines that describe the factorization. Each line has two numbers

x

$x$ and

k

$k$ where

x

$x$ is a prime and

k

$k$ is its power.

Output

Print three integers modulo

10^{9} + 7

$10^9+7$ : the number, sum and product of the divisors.

Constraints

$1 \le n \le 10^5$
$2 \le x \le 10^6$
each $x$ is a distinct prime
$1 \le k \le 10^9$

Example

Input:

Output:
6 28 1728

Prime Multiples

CSES - Prime Multiples

Time limit: 1.00 s
Memory limit: 512 MB

You are given

k

$k$ distinct prime numbers

a_{1}, a_{2}, \dots, a_{k}

$a_1,a_2,\ldots,a_k$ and an integer

n

$n$ .

Your task is to calculate how many of the first

n

$n$ positive integers are divisible by at least one of the given prime numbers.

Input

The first input line has two integers

n

$n$ and

k

$k$ .

The second line has

k

$k$ prime numbers

a_{1}, a_{2}, \dots, a_{k}

$a_1,a_2,\ldots,a_k$ .

Output

Print one integer: the number integers within the interval

1, 2, \dots, n

$1,2,\ldots,n$ that are divisible by at least one of the prime numbers.

Constraints

$1 \le n \le 10^{18}$
$1 \le k \le 20$
$2 \le a_i \le n$

Example

Input:

20 2

2 5

Output:
12

Explanation: the

12

$12$ numbers are

2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20

$2,4,5,6,8,10,12,14,15,16,18,20$ .

Counting Coprime Pairs

CSES - Counting Coprime Pairs

Time limit: 1.00 s
Memory limit: 512 MB

Given a list of

n

$n$ positive integers, your task is to count the number of pairs of integers that are coprime (i.e., their greatest common divisor is one).

Input

The first input line has an integer

n

$n$ : the number of elements.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ : the contents of the list.

Output

Print one integer: the answer for the task.

Constraints

$1 \le n \le 10^5$
$1 \le x_i \le 10^6$

Example

Input:

8

5 4 20 1 16 17 5 15

Output:
19

Binomial Coefficients

CSES - Binomial Coefficients

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate

n

$n$ binomial coefficients modulo

10^{9} + 7

$10^9+7$ .

A binomial coefficient

(\binom{a}{b})

${a \choose b}$ can be calculated using the formula

\frac{a!}{b! (a - b)!}

$\frac{a!}{b!(a-b)!}$ . We assume that

a

$a$ and

b

$b$ are integers and

0 \leq b \leq a

$0 \le b \le a$ .

Input

The first input line contains an integer

n

$n$ : the number of calculations.

After this, there are

n

$n$ lines, each of which contains two integers

a

$a$ and

b

$b$ .

Output

Print each binomial coefficient modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^5$
$0 \le b \le a \le 10^6$

Example

Input:

Output:

Creating Strings II

CSES - Creating Strings II

Time limit: 1.00 s
Memory limit: 512 MB

Given a string, your task is to calculate the number of different strings that can be created using its characters.

Input

The only input line has a string of length

n

$n$ . Each character is between a–z.

Output

Print the number of different strings modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^6$

Example

Input:
aabac

Output:
20

Distributing Apples

CSES - Distributing Apples

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ children and

m

$m$ apples that will be distributed to them. Your task is to count the number of ways this can be done.

For example, if

n = 3

$n=3$ and

m = 2

$m=2$ , there are

6

$6$ ways:

[0, 0, 2]

$[0,0,2]$ ,

[0, 1, 1]

$[0,1,1]$ ,

[0, 2, 0]

$[0,2,0]$ ,

[1, 0, 1]

$[1,0,1]$ ,

[1, 1, 0]

$[1,1,0]$ and

[2, 0, 0]

$[2,0,0]$ .

Input

The only input line has two integers

n

$n$ and

m

$m$ .

Output

Print the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n,m \le 10^6$

Example

Input:
3 2

Output:
6

Christmas Party

CSES - Christmas Party

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ children at a Christmas party, and each of them has brought a gift. The idea is that everybody will get a gift brought by someone else.

In how many ways can the gifts be distributed?

Input

The only input line has an integer

n

$n$ : the number of children.

Output

Print the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^6$

Example

Input:
4

Output:
9

Bracket Sequences I

CSES - Bracket Sequences I

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the number of valid bracket sequences of length

n

$n$ . For example, when

n = 6

$n=6$ , there are

5

$5$ sequences:

()()()
()(())
(())()
((()))
(()())

Input

The only input line has an integer

n

$n$ .

Output

Print the number of sequences modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^6$

Example

Input:
6

Output:
5

Bracket Sequences II

CSES - Bracket Sequences II

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the number of valid bracket sequences of length

n

$n$ when a prefix of the sequence is given.

Input

The first input line has an integer

n

$n$ .

The second line has a string of

k

$k$ characters: the prefix of the sequence.

Output

Print the number of sequences modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le k \le n \le 10^6$

Example

Input:

6

(()

Output:
2

Explanation: There are two possible sequences: (())() and (()()).

Counting Necklaces

CSES - Counting Necklaces

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count the number of different necklaces that consist of

n

$n$ pearls and each pearl has

m

$m$ possible colors.

Two necklaces are considered to be different if it is not possible to rotate one of them so that they look the same.

Input

The only input line has two numbers

n

$n$ and

m

$m$ : the number of pearls and colors.

Output

Print one integer: the number of different necklaces modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n,m \le 10^6$

Example

Input:
4 3

Output:
24

Counting Grids

CSES - Counting Grids

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to count the number of different

n \times n

$n \times n$ grids whose each square is black or white.

Two grids are considered to be different if it is not possible to rotate one of them so that they look the same.

Input

The only input line has an integer

n

$n$ : the size of the grid.

Output

Print one integer: the number of grids modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^9$

Example

Input:
4

Output:
16456

Fibonacci Numbers

CSES - Fibonacci Numbers

Time limit: 1.00 s
Memory limit: 512 MB

The Fibonacci numbers can be defined as follows:

$F_0=0$
$F_1=1$
$F_n = F_{n-2}+F_{n-1}$

Your task is to calculate the value of

F_{n}

$F_n$ for a given

n

$n$ .

Input

The only input line has an integer

n

$n$ .

Output

Print the value of

F_{n}

$F_n$ modulo

10^{9} + 7

$10^9+7$ .

Constraints

$0 \le n \le 10^{18}$

Example

Input:
10

Output:
55

Throwing Dice

CSES - Throwing Dice

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the number of ways to get a sum

n

$n$ by throwing dice. Each throw yields an integer between

1 \dots 6

$1 \ldots 6$ .

For example, if

n = 10

$n=10$ , some possible ways are

3 + 3 + 4

$3+3+4$ ,

1 + 4 + 1 + 4

$1+4+1+4$ and

1 + 1 + 6 + 1 + 1

$1+1+6+1+1$ .

Input

The only input line contains an integer

n

$n$ .

Output

Print the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 10^{18}$

Example

Input:
8

Output:
125

Graph Paths I

CSES - Graph Paths I

Time limit: 1.00 s
Memory limit: 512 MB

Consider a directed graph that has

n

$n$ nodes and

m

$m$ edges. Your task is to count the number of paths from node

1

$1$ to node

n

$n$ with exactly

k

$k$ edges.

Input

The first input line contains three integers

n

$n$ ,

m

$m$ and

k

$k$ : the number of nodes and edges, and the length of the path. The nodes are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are

m

$m$ lines describing the edges. Each line contains two integers

a

$a$ and

b

$b$ : there is an edge from node

a

$a$ to node

b

$b$ .

Output

Print the number of paths modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 100$
$1 \le m \le n(n-1)$
$1 \le k \le 10^9$
$1 \le a,b \le n$

Example

Input:

Output:
2

Explanation: The paths are

1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1 \to 2 \to 3

$1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3$ and

1 \to 2 \to 3 \to 2 \to 3 \to 2 \to 3 \to 2 \to 3

$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3$ .

Graph Paths II

CSES - Graph Paths II

Time limit: 1.00 s
Memory limit: 512 MB

Consider a directed weighted graph having

n

$n$ nodes and

m

$m$ edges. Your task is to calculate the minimum path length from node

1

$1$ to node

n

$n$ with exactly

k

$k$ edges.

Input

The first input line contains three integers

n

$n$ ,

m

$m$ and

k

$k$ : the number of nodes and edges, and the length of the path. The nodes are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are m lines describing the edges. Each line contains three integers

a

$a$ ,

b

$b$ and

c

$c$ : there is an edge from node

a

$a$ to node

b

$b$ with weight

c

$c$ .

Output

Print the minimum path length. If there are no such paths, print

- 1

$-1$ .

Constraints

$1 \le n \le 100$
$1 \le m \le n(n-1)$
$1 \le k \le 10^9$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
27

Graph Paths II

CSES - Graph Paths II

Time limit: 1.00 s
Memory limit: 512 MB

Consider a directed weighted graph having

n

$n$ nodes and

m

$m$ edges. Your task is to calculate the minimum path length from node

1

$1$ to node

n

$n$ with exactly

k

$k$ edges.

Input

The first input line contains three integers

n

$n$ ,

m

$m$ and

k

$k$ : the number of nodes and edges, and the length of the path. The nodes are numbered

1, 2, \dots, n

$1,2,\dots,n$ .

Then, there are m lines describing the edges. Each line contains three integers

a

$a$ ,

b

$b$ and

c

$c$ : there is an edge from node

a

$a$ to node

b

$b$ with weight

c

$c$ .

Output

Print the minimum path length. If there are no such paths, print

- 1

$-1$ .

Constraints

$1 \le n \le 100$
$1 \le m \le n(n-1)$
$1 \le k \le 10^9$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Example

Input:

Output:
27

Dice Probability

CSES - Dice Probability

Time limit: 1.00 s
Memory limit: 512 MB

You throw a dice

n

$n$ times, and every throw produces an outcome between

1

$1$ and

6

$6$ . What is the probability that the sum of outcomes is between

a

$a$ and

b

$b$ ?

Input

The only input line contains three integers

n

$n$ ,

a

$a$ and

b

$b$ .

Output

Print the probability rounded to six decimal places.

Constraints

$1 \le n \le 100$
$1 \le a \le b \le 6n$

Example

Input:
2 9 10

Output:
0.194444

Moving Robots

CSES - Moving Robots

Time limit: 1.00 s
Memory limit: 512 MB

Each square of an

8 \times 8

$8 \times 8$ chessboard has a robot. Each robot independently moves

k

$k$ steps, and there can be many robots on the same square.

On each turn, a robot moves one step left, right, up or down, but not outside the board. It randomly chooses a direction among those where it can move.

Your task is to calculate the expected number of empty squares after

k

$k$ turns.

Input

The only input line has an integer

k

$k$ .

Output

Print the expected number of empty squares rounded to six decimal places.

Constraints

$1 \le k \le 100$

Example

Input:
10

Output:
23.120740

Candy Lottery

CSES - Candy Lottery

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ children, and each of them independently gets a random integer number of candies between

1

$1$ and

k

$k$ .

What is the expected maximum number of candies a child gets?

Input

The only input line contains two integers

n

$n$ and

k

$k$ .

Output

Print the expected number rounded to six decimal places.

Constraints

$1 \le n \le 100$
$1 \le k \le 100$

Example

Input:
2 3

Output:
2.444444

Inversion Probability

CSES - Inversion Probability

Time limit: 1.00 s
Memory limit: 512 MB

An array has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\dots,x_n$ , and each of them has been randomly chosen between

1

$1$ and

r_{i}

$r_i$ . An inversion is a pair

(a, b)

$(a,b)$ where

a < b

$a<b$ and

x_{a} > x_{b}

$x_a>x_b$ .

What is the expected number of inversions in the array?

Input

The first input line contains an integer

n

$n$ : the size of the array.

The second line contains

n

$n$ integers

r_{1}, r_{2}, \dots, r_{n}

$r_1,r_2,\dots,r_n$ : the range of possible values for each array position.

Output

Print the expected number of inversions rounded to six decimal places.

Constraints

$1 \le n \le 100$
$1 \le r_i \le 100$

Example

Input:

3

5 2 7

Output:
1.057143

Stick Game

CSES - Stick Game

Time limit: 1.00 s
Memory limit: 512 MB

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set

P = {p_{1}, p_{2}, \dots, p_{k}}

$P=\{p_1,p_2,\ldots,p_k\}$ determines the allowed moves. For example, if

P = {1, 3, 4}

$P=\{1,3,4\}$ , a player may remove

1

$1$ ,

3

$3$ or

4

$4$ sticks.

Your task is find out for each number of sticks

1, 2, \dots, n

$1,2,\dots,n$ if the first player has a winning or losing position.

Input

The first input line has two integers

n

$n$ and

k

$k$ : the number of sticks and moves.

The next line has

k

$k$ integers

p_{1}, p_{2}, \dots, p_{k}

$p_1,p_2,\dots,p_k$ that describe the allowed moves. All integers are distinct, and one of them is

1

$1$ .

Output

Print a string containing

n

$n$ characters: W means a winning position, and L means a losing position.

Constraints

$1 \le n \le 10^6$
$1 \le k \le 100$
$1 \le p_i \le n$

Example

Input:

10 3

1 3 4

Output:
WLWWWWLWLW

Nim Game I

CSES - Nim Game I

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer

t

$t$ : the number of tests. After this,

t

$t$ test cases are described:

The first line contains an integer

n

$n$ : the number of heaps.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the number of sticks in each heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints

$1 \le t \le 2 \cdot 10^5$
$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
the sum of all $n$ is at most $2 \cdot 10^5$

Example

Input:

Output:

first

first

second

Nim Game II

CSES - Nim Game II

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes

1

$1$ ,

2

$2$ , or

3

$3$ sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer

t

$t$ : the number of tests. After this,

t

$t$ test cases are described:

The first line contains an integer

n

$n$ : the number of heaps.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$1 \le t \le 2 \cdot 10^5$
$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
the sum of all $n$ is at most $2 \cdot 10^5$

Example

Input:

Output:

first

first

second

Stair Game

CSES - Stair Game

Time limit: 1.00 s
Memory limit: 512 MB

There is a staircase consisting of

n

$n$ stairs, numbered

1, 2, \dots, n

$1,2,\ldots,n$ . Initially, each stair has some number of balls.

There are two players who move alternately. On each move, a player chooses a stair

k

$k$ where

k \neq 1

$k \neq 1$ and it has at least one ball. Then, the player moves any number of balls from stair

k

$k$ to stair

k - 1

$k-1$ . The player who moves last wins the game.

Your task is to find out who wins the game when both players play optimally.

Note that if there are no possible moves at all, the second player wins.

Input

The first input line has an integer

t

$t$ : the number of tests. After this,

t

$t$ test cases are described:

The first line contains an integer

n

$n$ : the number of stairs.

The next line has

n

$n$ integers

p_{1}, p_{2}, \dots, p_{n}

$p_1,p_2,\ldots,p_n$ : the initial number of balls on each stair.

Output

For each test, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints

$1 \le t \le 2 \cdot 10^5$
$1 \le n \le 2 \cdot 10^5$
$0 \le p_i \le 10^9$
the sum of all $n$ is at most $2 \cdot 10^5$

Example

Input:

Output:

first

second

first

Grundy's Game

CSES - Grundy's Game

Time limit: 1.00 s
Memory limit: 512 MB

There is a heap of

n

$n$ coins and two players who move alternately. On each move, a player chooses a heap and divides into two nonempty heaps that have a different number of coins. The player who makes the last move wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer

t

$t$ : the number of tests.

After this, there are

t

$t$ lines that describe the tests. Each line has an integer

n

$n$ : the number of coins in the initial heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints

$1 \le t \le 10^5$
$1 \le n \le 10^6$

Example

Input:

Output:

first

second

first

Another Game

CSES - Another Game

Time limit: 1.00 s
Memory limit: 512 MB

There are

n

$n$ heaps of coins and two players who move alternately. On each move, a player selects some of the nonempty heaps and removes one coin from each heap. The player who removes the last coin wins the game.

Your task is to find out who wins if both players play optimally.

Input

The first input line contains an integer

t

$t$ : the number of tests. After this,

t

$t$ test cases are described:

The first line contains an integer

n

$n$ : the number of heaps.

The next line has

n

$n$ integers

x_{1}, x_{2}, \dots, x_{n}

$x_1,x_2,\ldots,x_n$ : the number of coins in each heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints

$1 \le t \le 2 \cdot 10^5$
$1 \le n \le 2 \cdot 10^5$
$1 \le x_i \le 10^9$
the sum of all $n$ is at most $2 \cdot 10^5$

Example

Input:

Output:

first

second

first

Word Combinations

CSES - Word Combinations

Time limit: 1.00 s
Memory limit: 512 MB

You are given a string of length

n

$n$ and a dictionary containing

k

$k$ words. In how many ways can you create the string using the words?

Input

The first input line has a string containing

n

$n$ characters between a–z.

The second line has an integer

k

$k$ : the number of words in the dictionary.

Finally there are

k

$k$ lines describing the words. Each word is unique and consists of characters a–z.

Output

Print the number of ways modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 5000$
$1 \le k \le 10^5$
the total length of the words is at most $10^6$

Example

Input:

ababc

4

ab

abab

c

cb

Output:
2

Explanation: The possible ways are ab+ab+c and abab+c.

String Matching

CSES - String Matching

Time limit: 1.00 s
Memory limit: 512 MB

Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.

Input

The first input line has a string of length

n

$n$ , and the second input line has a pattern of length

m

$m$ . Both of them consist of characters a–z.

Output

Print one integer: the number of occurrences.

Constraints

$1 \le n,m \le 10^6$

Example

Input:

saippuakauppias

pp

Output:
2

Finding Borders

CSES - Finding Borders

Time limit: 1.00 s
Memory limit: 512 MB

A border of a string is a prefix that is also a suffix of the string but not the whole string. For example, the borders of abcababcab are ab and abcab.

Your task is to find all border lengths of a given string.

Input

The only input line has a string of length

n

$n$ consisting of characters a–z.

Output

Print all border lengths of the string in increasing order.

Constraints

$1 \le n \le 10^6$

Example

Input:
abcababcab

Output:
2 5

Finding Periods

CSES - Finding Periods

Time limit: 1.00 s
Memory limit: 512 MB

A period of a string is a prefix that can be used to generate the whole string by repeating the prefix. The last repetition may be partial. For example, the periods of abcabca are abc, abcabc and abcabca.

Your task is to find all period lengths of a string.

Input

The only input line has a string of length

n

$n$ consisting of characters a–z.

Output

Print all period lengths in increasing order.

Constraints

$1 \le n \le 10^6$

Example

Input:
abcabca

Output:
3 6 7

Minimal Rotation

CSES - Minimal Rotation

Time limit: 1.00 s
Memory limit: 512 MB

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

Input

The only input line contains a string of length

n

$n$ . Each character is one of a–z.

Output

Print the lexicographically minimal rotation.

Constraints

$1 \le n \le 10^6$

Example

Input:
acab

Output:
abac

Longest Palindrome

CSES - Longest Palindrome

Time limit: 1.00 s
Memory limit: 512 MB

Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab.

Input

The only input line contains a string of length

n

$n$ . Each character is one of a–z.

Output

Print the longest palindrome in the string. If there are several solutions, you may print any of them.

Constraints

$1 \le n \le 10^6$

Example

Input:
aybabtu

Output:
bab

Required Substring

CSES - Required Substring

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the number of strings of length

n

$n$ having a given pattern of length

m

$m$ as their substring. All strings consist of characters A–Z.

Input

The first input line has an integer

n

$n$ : the length of the final string.

The second line has a pattern of length

m

$m$ .

Output

Print the number of strings modulo

10^{9} + 7

$10^9+7$ .

Constraints

$1 \le n \le 1000$
$1 \le m \le 100$

Example

Input:

6

ABCDB

Output:
52

Explanation: The final string will be of the form ABCDB

x

$x$ or

x

$x$ ABCDB where

x

$x$ is any character between A–Z.

Palindrome Queries

CSES - Palindrome Queries

Time limit: 1.00 s
Memory limit: 512 MB

You are given a string that consists of

n

$n$ characters between a–z. The positions of the string are indexed

1, 2, \dots, n

$1,2,\dots,n$ .

Your task is to process

m

$m$ operations of the following types:

Change the character at position $k$ to $x$
Check if the substring from position $a$ to position $b$ is a palindrome

Input

The first input line has two integers

n

$n$ and

m

$m$ : the length of the string and the number of operations.

The next line has a string that consists of

n

$n$ characters.

Finally, there are

m

$m$ lines that describe the operations. Each line is of the form "1

k

$k$

x

$x$ " or "2

a

$a$

b

$b$ ".

Output

For each operation 2, print YES if the substring is a palindrome and NO otherwise.

Constraints

$1 \le n, m \le 2 \cdot 10^5$
$1 \le k \le n$
$1 \le a \le b \le n$

Example

Input:

Output:

YES

NO

YES

Finding Patterns

CSES - Finding Patterns

Time limit: 1.00 s
Memory limit: 512 MB

Given a string and patterns, check for each pattern if it appears in the string.

Input

The first input line has a string of length

n

$n$ .

The next input line has an integer

k

$k$ : the number of patterns. Finally, there are

k

$k$ lines that describe the patterns.

The string and the patterns consist of characters a–z.

Output

For each pattern, print "YES" if it appears in the string and "NO" otherwise.

Constraints

$1 \le n \le 10^5$
$1 \le k \le 5 \cdot 10^5$
the total length of the patterns is at most $5 \cdot 10^5$

Example

Input:

aybabtu

3

bab

abc

ayba

Output:

YES

NO

YES

Counting Patterns

CSES - Counting Patterns

Time limit: 1.00 s
Memory limit: 512 MB

Given a string and patterns, count for each pattern the number of positions where it appears in the string.

Input

The first input line has a string of length

n

$n$ .

The next input line has an integer

k

$k$ : the number of patterns. Finally, there are

k

$k$ lines that describe the patterns.

The string and the patterns consist of characters a–z.

Output

For each pattern, print the number of positions.

Constraints

$1 \le n \le 10^5$
$1 \le k \le 5 \cdot 10^5$
the total length of the patterns is at most $5 \cdot 10^5$

Example

Input:

aybabtu

3

bab

abc

a

Output:

Pattern Positions

CSES - Pattern Positions

Time limit: 1.00 s
Memory limit: 512 MB

Given a string and patterns, find for each pattern the first position (1-indexed) where it appears in the string.

Input

The first input line has a string of length

n

$n$ .

The next input line has an integer

k

$k$ : the number of patterns. Finally, there are

k

$k$ lines that describe the patterns.

The string and the patterns consist of characters a–z.

Output

Print the first position for each pattern (or

- 1

$-1$ if it does not appear at all).

Constraints

$1 \le n \le 10^5$
$1 \le k \le 5 \cdot 10^5$
the total length of the patterns is at most $5 \cdot 10^5$

Example

Input:

aybabtu

3

bab

abc

a

Output:

Distinct Substrings

CSES - Distinct Substrings

Time limit: 1.00 s
Memory limit: 512 MB

Count the number of distinct substrings that appear in a string.

Input

The only input line has a string of length

n

$n$ that consists of characters a–z.

Output

Print one integer: the number of substrings.

Constraints

$1 \le n \le 10^5$

Example

Input:
abaa

Output:
8

Explanation: the substrings are a, b, aa, ab, ba, aba, baa and abaa.

Repeating Substring

CSES - Repeating Substring

Time limit: 1.00 s
Memory limit: 512 MB

A repeating substring is a substring that occurs in two (or more) locations in the string. Your task is to find the longest repeating substring in a given string.

Input

The only input line has a string of length

n

$n$ that consists of characters a–z.

Output

Print the longest repeating substring. If there are several possibilities, you can print any of them. If there is no repeating substring, print

- 1

$-1$ .

Constraints

$1 \le n \le 10^5$

Example

Input:
cabababc

Output:
abab

String Functions

CSES - String Functions

Time limit: 1.00 s
Memory limit: 512 MB

We consider a string of

n

$n$ characters, indexed

1, 2, \dots, n

$1,2,\dots,n$ . Your task is to calculate all values of the following functions:

$z(i)$ denotes the maximum length of a substring that begins at position $i$ and is a prefix of the string. In addition, $z(1)=0$ .
$\pi(i)$ denotes the maximum length of a substring that ends at position $i$ , is a prefix of the string, and whose length is at most $i-1$ .

Note that the function

z

$z$ is used in the Z-algorithm, and the function

π

$\pi$ is used in the KMP algorithm.

Input

The only input line has a string of length

n

$n$ . Each character is between a–z.

Output

Print two lines: first the values of the

z

$z$ function, and then the values of the

π

$\pi$ function.

Constraints

$1 \le n \le 10^6$

Example

Input:
abaabca

Output:

0 0 1 2 0 0 1

0 0 1 1 2 0 1

Substring Order I

CSES - Substring Order I

Time limit: 1.00 s
Memory limit: 512 MB

You are given a string of length

n

$n$ . If all of its distinct substrings are ordered lexicographically, what is the

k

$k$ th smallest of them?

Input

The first input line has a string of length

n

$n$ that consists of characters a–z.

The second input line has an integer

k

$k$ .

Output

Print the

k

$k$ th smallest distinct substring in lexicographical order.

Constraints

$1 \le n \le 10^5$
$1 \le k \le \frac{n(n+1)}{2}$
It is guaranteed that $k$ does not exceed the number of distinct substrings.

Example

Input:

babaacbaab

10

Output:
aba

Explanation: The 10 smallest distinct substrings in order are a, aa, aab, aac, aacb, aacba, aacbaa, aacbaab, ab, and aba.

Substring Order II

CSES - Substring Order II

Time limit: 1.00 s
Memory limit: 512 MB

You are given a string of length

n

$n$ . If all of its substrings (not necessarily distinct) are ordered lexicographically, what is the

k

$k$ th smallest of them?

Input

The first input line has a string of length

n

$n$ that consists of characters a–z.

The second input line has an integer

k

$k$ .

Output

Print the

k

$k$ th smallest substring in lexicographical order.

Constraints

$1 \le n \le 10^5$
$1 \le k \le \frac{n(n+1)}{2}$

Example

Input:

baabaa

10

Output:
ab

Explanation: The 10 smallest substrings in order are a, a, a, a, aa, aa, aab, aaba, aabaa, and ab.

Substring Distribution

CSES - Substring Distribution

Time limit: 1.00 s
Memory limit: 512 MB

You are given a string of length

n

$n$ . For every integer between

1 \dots n

$1 \ldots n$ you need to print the number of distinct substrings of that length.

Input

The only input line has a string of length

n

$n$ that consists of characters a–z.

Output

For each integer between

1 \dots n

$1 \ldots n$ print the number of distinct substrings of that length.

Constraints

$1 \le n \le 10^5$

Example

Input:
abab

Output:
2 2 2 1

Geometry

Point Location Test

CSES - Point Location Test

Time limit: 1.00 s
Memory limit: 512 MB

There is a line that goes through the points

p_{1} = (x_{1}, y_{1})

$p_1=(x_1,y_1)$ and

p_{2} = (x_{2}, y_{2})

$p_2=(x_2,y_2)$ . There is also a point

p_{3} = (x_{3}, y_{3})

$p_3=(x_3,y_3)$ .

Your task is to determine whether

p_{3}

$p_3$ is located on the left or right side of the line or if it touches the line when we are looking from

p_{1}

$p_1$ to

p_{2}

$p_2$ .

Input

The first input line has an integer

t

$t$ : the number of tests.

After this, there are

t

$t$ lines that describe the tests. Each line has six integers:

x_{1}

$x_1$ ,

y_{1}

$y_1$ ,

x_{2}

$x_2$ ,

y_{2}

$y_2$ ,

x_{3}

$x_3$ and

y_{3}

$y_3$ .

Output

For each test, print "LEFT", "RIGHT" or "TOUCH".

Constraints

$1 \le t \le 10^5$
$-10^9 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 10^9$
$x_1 \neq x_2$ or $y_1 \neq y_2$

Example

Input:

3

1 1 5 3 2 3

1 1 5 3 4 1

1 1 5 3 3 2

Output:

LEFT

RIGHT

TOUCH

Line Segment Intersection

CSES - Line Segment Intersection

Time limit: 1.00 s
Memory limit: 512 MB

There are two line segments: the first goes through the points

(x_{1}, y_{1})

$(x_1,y_1)$ and

(x_{2}, y_{2})

$(x_2,y_2)$ , and the second goes through the points

(x_{3}, y_{3})

$(x_3,y_3)$ and

(x_{4}, y_{4})

$(x_4,y_4)$ .

Your task is to determine if the line segments intersect, i.e., they have at least one common point.

Input

The first input line has an integer

t

$t$ : the number of tests.

After this, there are

t

$t$ lines that describe the tests. Each line has eight integers

x_{1}

$x_1$ ,

y_{1}

$y_1$ ,

x_{2}

$x_2$ ,

y_{2}

$y_2$ ,

x_{3}

$x_3$ ,

y_{3}

$y_3$ ,

x_{4}

$x_4$ and

y_{4}

$y_4$ .

Output

For each test, print "YES" if the line segments intersect and "NO" otherwise.

Constraints

$1 \le t \le 10^5$
$-10^9 \le x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \le 10^9$
$(x_1,y_1) \neq (x_2,y_2)$
$(x_3,y_3) \neq (x_4,y_4)$

Example

Input:

5

1 1 5 3 1 2 4 3

1 1 5 3 1 1 4 3

1 1 5 3 2 3 4 1

1 1 5 3 2 4 4 1

1 1 5 3 3 2 7 4

Output:

NO

YES

YES

YES

YES

Polygon Area

CSES - Polygon Area

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to calculate the area of a given polygon.

The polygon consists of

n

$n$ vertices

(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})

$(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ . The vertices

(x_{i}, y_{i})

$(x_i,y_i)$ and

(x_{i + 1}, y_{i + 1})

$(x_{i+1},y_{i+1})$ are adjacent for

i = 1, 2, \dots, n - 1

$i=1,2,\dots,n-1$ , and the vertices

(x_{1}, y_{1})

$(x_1,y_1)$ and

(x_{n}, y_{n})

$(x_n,y_n)$ are also adjacent.

Input

The first input line has an integer

n

$n$ : the number of vertices.

After this, there are

n

$n$ lines that describe the vertices. The

i

$i$ th such line has two integers

x_{i}

$x_i$ and

y_{i}

$y_i$ .

You may assume that the polygon is simple, i.e., it does not intersect itself.

Output

Print one integer:

2 a

$2a$ where the area of the polygon is

a

$a$ (this ensures that the result is an integer).

Constraints

$3 \le n \le 1000$
$-10^9 \le x_i, y_i \le 10^9$

Example

Input:

Output:
16

Point in Polygon

CSES - Point in Polygon

Time limit: 1.00 s
Memory limit: 512 MB

You are given a polygon of

n

$n$ vertices and a list of

m

$m$ points. Your task is to determine for each point if it is inside, outside or on the boundary of the polygon.

The polygon consists of

n

$n$ vertices

(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})

$(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ . The vertices

(x_{i}, y_{i})

$(x_i,y_i)$ and

(x_{i + 1}, y_{i + 1})

$(x_{i+1},y_{i+1})$ are adjacent for

i = 1, 2, \dots, n - 1

$i=1,2,\dots,n-1$ , and the vertices

(x_{1}, y_{1})

$(x_1,y_1)$ and

(x_{n}, y_{n})

$(x_n,y_n)$ are also adjacent.

Input

The first input line has two integers

n

$n$ and

m

$m$ : the number of vertices in the polygon and the number of points.

After this, there are

n

$n$ lines that describe the polygon. The

i

$i$ th such line has two integers

x_{i}

$x_i$ and

y_{i}

$y_i$ .

You may assume that the polygon is simple, i.e., it does not intersect itself.

Finally, there are

m

$m$ lines that describe the points. Each line has two integers

x

$x$ and

y

$y$ .

Output

For each point, print "INSIDE", "OUTSIDE" or "BOUNDARY".

Constraints

$3 \le n,m \le 1000$
$1 \le m \le 1000$
$-10^9 \le x_i, y_i \le 10^9$
$-10^9 \le x, y \le 10^9$

Example

Input:

Output:

INSIDE

OUTSIDE

BOUNDARY

Polygon Lattice Points

CSES - Polygon Lattice Points

Time limit: 1.00 s
Memory limit: 512 MB

Given a polygon, your task is to calculate the number of lattice points inside the polygon and on its boundary. A lattice point is a point whose coordinates are integers.

The polygon consists of

n

$n$ vertices

(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})

$(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ . The vertices

(x_{i}, y_{i})

$(x_i,y_i)$ and

(x_{i + 1}, y_{i + 1})

$(x_{i+1},y_{i+1})$ are adjacent for

i = 1, 2, \dots, n - 1

$i=1,2,\dots,n-1$ , and the vertices

(x_{1}, y_{1})

$(x_1,y_1)$ and

(x_{n}, y_{n})

$(x_n,y_n)$ are also adjacent.

Input

The first input line has an integer

n

$n$ : the number of vertices.

After this, there are

n

$n$ lines that describe the vertices. The

i

$i$ th such line has two integers

x_{i}

$x_i$ and

y_{i}

$y_i$ .

You may assume that the polygon is simple, i.e., it does not intersect itself.

Output

Print two integers: the number of lattice points inside the polygon and on its boundary.

Constraints

$3 \le n \le 10^5$
$-10^6 \le x_i, y_i \le 10^6$

Example

Input:

Output:
6 8

Minimum Euclidean Distance

CSES - Minimum Euclidean Distance

Time limit: 1.00 s
Memory limit: 512 MB

Given a set of points in the two-dimensional plane, your task is to find the minimum Euclidean distance between two distinct points.

The Euclidean distance of points

(x_{1}, y_{1})

$(x_1,y_1)$ and

(x_{2}, y_{2})

$(x_2,y_2)$ is

\sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}

$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ .

Input

The first input line has an integer

n

$n$ : the number of points.

After this, there are

n

$n$ lines that describe the points. Each line has two integers

x

$x$ and

y

$y$ . You may assume that each point is distinct.

Output

Print one integer:

d^{2}

$d^2$ where

d

$d$ is the minimum Euclidean distance (this ensures that the result is an integer).

Constraints

$2 \le n \le 2 \cdot 10^5$
$-10^9 \le x,y \le 10^9$

Example

Input:

Output:
2

Convex Hull

CSES - Convex Hull

Time limit: 1.00 s
Memory limit: 512 MB

Given a set of

n

$n$ points in the two-dimensional plane, your task is to determine the convex hull of the points.

Input

The first input line has an integer

n

$n$ : the number of points.

After this, there are

n

$n$ lines that describe the points. Each line has two integers

x

$x$ and

y

$y$ : the coordinates of a point.

You may assume that each point is distinct, and the area of the hull is positive.

Output

First print an integer

k

$k$ : the number of points in the convex hull.

After this, print

k

$k$ lines that describe the points. You can print the points in any order. Print all points that lie on the convex hull.

Constraints

$3 \le n \le 2 \cdot 10^5$
$-10^9 \le x, y \le 10^9$

Example

Input:

Output:

De Bruijn Sequence

CSES - De Bruijn Sequence

Mail Delivery

CSES - Mail Delivery

Time limit: 1.00 s
Memory limit: 512 MB

n

$n$ and

m

$m$ : the number of crossings and streets. The crossings are numbered

1, 2, \dots, n

$1,\,2,\ldots,\,n$ , and the post office is located at crossing

1

$1$ .

After that, there are m lines describing the streets. Each line has two integers

a

$a$ and

b

$b$ : there is a street between crossings

a

$a$ and

b

2 \leq n \leq 10^{5}

$2\leq n\leq 10^5$

1 \leq m \leq 2 . 10^{5}

$1\leq m\leq 2 . 10^5$

1 \leq a, b \leq n

$1\leq a,\,b\leq n$

Example

Input:

Output:
1 2 6 3 2 4 5 3 1

Time limit: 1.00 s
Memory limit: 512 MB

Your task is to construct a minimum-length bit string that contains all possible substrings of length

n

$n$ . For example, when

n = 2

$n=2$ , the string 00110 is a valid solution, because its substrings of length

2

$2$ are 00, 01, 10 and 11.

Input

The only input line has an integer

n

$n$ .

Output

Print a minimum-length bit string that contains all substrings of length

n

$n$ . You can print any valid solution.

Constraints

$1 \le n \le 15$

Example

Input:
2

Output:
00110

Weired Algorithm

Missing Number

Repetitions

Increasing Array

Permutations

Number Spiral

Bit Strings

Trailing Zeroes

Coin Piles

Palinderome Reorder

Gray Code

Tower of Hanoi

Tower of Hanoi

Creating Strings

Apple Division

Chessboard and Queens

Digit Queries

Grid Paths

Sorting and Searching

Distinct Numbers

Apartments

Ferris Wheel

Concert Tickets

Restaurant Customers

Movie Festival

Sum of Two Values

Maximum Subarray Sum

Stick Lengths

Missing Coin Sum

Collecting NUmbers

Collecting Numbers II

PLaylist

Towers

Traffic Lights

Joshephus Problem I

Joshephus Problem II

Nested Ranges Check

Nested Ranges Count

Room Allocation

Factory Machines

Task and Deadlines

Reading Books

Sum Of Three Values

Sum of Four Values

Nearest Smaller Values

Subarray Sums I

Subarray Sums II

Subarray Divisibility

Subarray Distinct Values

Array Division

Sliding Median

Sliding Cost

Movie Festival II

Maximum Subarraysum II

Dynamic Programming

Dice Combinations

Minimizing Coins

Coin Combinations I

Coin COmbinations II

Removing Digits

Grid Paths

Book Shop

Array Description

Counting Towers

Edit Distance

Rectangle Cutting

Money Sums

Removal Game

Two Sets II

Increasing Subsequence

Increasing Subsequence

Increasing Subsquence

Projects

Elevator Rides

Counting Tilings

Counting Numbers

Graph Algorithms

Counting Rooms

Labyrinth

Building Roads